利用栈实现中缀表达式计算
如下图
根据用户输入的表达式，得出计算结果
思路分析
本题看似简单，实则不然，要实现这个功能我们不能简单的直接将这个字符串丢给程序 如下
int a = 7*2*2-5+1-5*3-3 // 3我们要模拟计算机是如何解析，并计算出这样一个字符串的结果。
如果我们自己实现这样一个功能，至少会涉及到，数字拆分、运算符解析、运算符优先级计算。 这里就可以利用栈先入后出的特点完成该程序
大体思路如下
首先创建两个栈—-数字栈和符号栈
1.通过一个index值（索引）来遍历表达式
2.当遍历的元素是数字时，将其放入数字栈中
3.当遍历的元素是符号时，就分为如下情况
3.1 如果发现当前的符号栈为空，就直接入符号栈
3.2 当前的符号栈不为空，要进行比比较
3.2.1如果当前的符号的优先级小于或等于栈顶中的符号。就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，并进行运算，将得到的结果放入数栈，在将当前符号放入符号栈
3.2.2 如果当前的符号的优先级大于栈顶中的符号。则直接入符号栈
4.当表达式遍历完毕时，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算
5.最后数栈中只有一个数字，即最后的结果
图示
如下例计算 3+2*6-2
第一次扫描时，发现是数字，将其放入数栈中。
第二次扫描时，发现是符号，并且当前符号栈为空，所以直接放入符号栈
第三次扫描时，发现是数字，将其放入数栈中
第四次扫描时，发现是符号（*），并且当前符号的优先级是大于符号栈，栈顶符号的优先级的。此时直接入符号栈
第五次扫描时，发现是数字，直接放入数字栈中
第六次扫描发现是符号（-）,并且当前符号的优先级是小于栈顶符号（*）的优先级，此时在数栈中弹出两个数（6和2），符号栈中弹出一个符号(*)，将它们进行运算得到结果12，并将结果放入数栈中，同时将当前符号（- ）放入到符号栈中
第七次扫描，发现是数字，直接将其放入数栈中
此时已经遍历完毕，接下来要将数栈和符号栈中的元素分别弹出进行运算 第一次弹出 12和2和-运算得到结果为10，并将其放入数栈中
此时，在弹出数栈和符号栈中的元素 10和3和+，得到运算结果为13，将其放入数栈中 此时数栈中只有一个元素即表达式运算的结果
代码实现
首先用数组模拟栈，创建一个栈类
class ArrayStack{
private int maxSize;
private int[] stack; //栈数组
private int top = -1; //栈顶
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
//判断栈是否满
public boolean isFull(){
return top == maxSize - 1;
}
//栈是否为空
public boolean isEmpty(){
return top == -1;
}
//入栈
public void push(int value){
if(isFull()){
System.out.println("栈已满，不能放");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
int value = stack[top];
top--;
return value;
}
//显示栈中的元素
public void list(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
//从栈顶开始显示数据
for(int i = top ; i >= 0 ;i--){
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}为了后面方便计算，我们还得给栈添加几个方法 1.查看栈顶中的元素 2.计算符号优先级 3.判断是否为运算符 4.计算方法
...
//查看栈顶的元素,而不是弹出
public int peek(){
return stack[top];
}
//返回运算符优先级，数字越大优先级越高
public int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
}else if (oper == '+' || oper == '-'){
return 0;
}else{
return -1;
}
}
//判断是否为运算符
public boolean isOper(char val){
return val == '+' || val == '-' || val == '*' || val == '/';
}
//计算
public int cal(int num1,int num2, int oper){
int res = 0; //计算的结果
switch (oper){
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}接下来完成我们的程序
public static void main(String[] args) {
//运算的表达式
String expr = "3+2*6-2";
//创建数栈和符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
int index = 0; //用于遍历表达式
int num1 = 0;
int num2 = 0;
int oper = 0; //运算符
int res = 0; //运算后的结果
char ch = ' '; //将每次扫描得到的char保存到ch
//while循环扫描表达式
while (true){
//依次扫描expr
ch = expr.substring(index,index+1).charAt(0);
//判断 ch 是数字还是符号
if(operStack.isOper(ch)){
//ch是运算符
if(operStack.isEmpty()){
//如果符号栈为空则直接入栈
operStack.push(ch);
}else{
/*符号栈不为空
判断符号的优先级是否大于栈顶符号的优先级
直接放入符号栈顶
判断符号的优先级是否小于等于栈顶符号的优先级
从数栈pop两个数，并和栈顶符号运算
*/
if(operStack.priority(ch) <= operStack.priority(operStack.peek())){
//进行运算
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1,num2,oper);
numStack.push(res); //将运算的结果入数栈
operStack.push(ch); //并将当前的符号入符号栈
}else{
//符号的优先级是否大于栈顶符号的优先级，直接入栈
operStack.push(ch);
}
}
}else{
//不是符号，认为是数字，直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
numStack.push(ch - 48);
}
index ++;
//扫描到最后退出循环
if(index >= expr.length()){
break;
}
}
//当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号进行计算
while (true){
//当符号栈为空时，说明计算到最后的结果了，数栈中只有一个数字即结果
if(operStack.isEmpty()){
break;
}
//进行运算
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1,num2,oper);
numStack.push(res); //将运算的结果入数栈
}
//将数栈的最后一个元素pop出来，即最后的结果
System.out.printf("表达式 %s = %d",expr,numStack.pop());
}测试得到结果如下
表达式 3+2*6-2 = 13可以看到结果和我们预期的一样，但是目前我们的程序还有问题
如果我们把表达式改成
expr = "30+2*6-2"; 最后输出结果为
表达式 3+2*6-2 = 10显然结果不对，这里就涉及到如何解决多位数的问题
问题就在在段代码中
...
else{
//不是符号，认为是数字，直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
numStack.push(ch - 48);
}
...我们直接将数放入栈中了，没有考虑到多为数的问题
解决这个问题的思路如下 1.在处理数字时，不能一发现数字就立即入栈 2.在处理数字时，需要向表达式的index后移一位，如果是数字则继续扫描，如果是符号才入栈 3.我们需要定义一个变量字符串，用于拼接拼接多为数
...
int num1 = 0;
int num2 = 0;
int oper = 0; //运算符
int res = 0; //运算后的结果
char ch = ' '; //将每次扫描得到的char保存到ch
String keepNum = "";//用于拼接多位数
......
else{
//不是符号，认为是数字，直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
//处理多位数问题
keepNum += ch;
//如果 ch 是 表达式的最后一位则直接入栈
if(index == expr.length() - 1){
numStack.push(Integer.parseInt(keepNum));
}else{
//判断 ch 下一个字符是否为符号，如果是直接入栈
if(operStack.isOper(expr.substring(index+1,index+2).charAt(0))){
numStack.push(Integer.parseInt(keepNum));
keepNum = "";//清空keepNum
}
}
}
...再次运行得到正确的结果
表达式 30+2*6-2 = 40腾讯云开发者
