栈实现综合计算器(中缀表达式)
程序员文章站
2022-05-26 12:01:26
...
栈: 计算器–运算
思路:
- 自己定义符号优先级 priority
- 判断是否为符号 isOper
- 进行运算 cal
- 需要两个栈 — 数栈、符号栈
- 定义需要的相关变量 index、num1、num2、res、oper、ch
- 分解表达式
- 判断当前字符 是 数字 还是 符号
7.1 如果是数字,直接压入数栈中
7.2 如果是符号
7.2.1 判断符号栈是否为空
7.2.2 为空: 将符号直接压入
7.2.3 不为空: 判断当前符号 与 符号栈栈顶符号的优先级谁高
7.2.4 当前符号优先级 小于等于 栈顶符号优先级: 将数栈中的pop出两个数,符号栈中pop一个进行运算,运算完后将 res 放入数栈, 然后再将当前符号压入符号栈中。
7.2.5 当前符号优先级 大于 栈顶符号优先级: 直接压入符号栈
7.3 判断是否分解到表达式末尾
7.4 表达式分解完后,对两个栈中剩下的数据进行运算: 数栈pop两个,符号栈pop一个。
7.5 运算完成的标志: 符号栈为空
7.6 最后数栈剩下的就是总运算结果
/**
* 数组模拟栈
*/
class ArrayStack<T> {
// 部分方法
/**
* 返回栈顶数据, 不弹出
*/
public T peek(){
return arr[top];
}
/**
* 定义优先级,符号优先级是我们自己来定义的
* 以数字来表示优先级高低
*/
public int prioprity(char oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1; // 目前只支持 + - * /
}
}
/**
* 判断是否为符号
*/
public boolean isOper(char oper) {
return oper == '*' || oper == '/' || oper == '+' || oper == '-';
}
/**
* 数运算
*/
public int cal(int num1, int num2, char oper) {
int res = 0;
// 实际需要考虑 / 0
switch (oper) {
case '*': res = num1 * num2;
break;
case '/': res = num2 / num1;
break;
case '+': res = num1 + num2;
break;
case '-': res = num2 - num1;
break;
default:
}
return res;
}
}
@Test
public void testOperStack(){
String exp = "3+6*2-2";
// 需要两个栈
// 数栈
ArrayStack numStack = new ArrayStack(10);
// 符号栈
ArrayStack operStack = new ArrayStack(10);
// 定义需要的相关变量
int index = 0; // 用于扫描
int res = 0;
char oper = 0;
int num1 = 0;
int num2 = 0;
char ch = ' '; // 用来接收表达式的字符
while (true){
ch = exp.charAt(index++);
// 判断是否为符号
if(operStack.isOper(ch)){
// 判断符号栈是否为空
if(operStack.isEmpty()){
operStack.push(ch);
}else{
// 不为空
// 判断当前符号与栈顶符号的优先级
if(operStack.prioprity(ch) <= operStack.prioprity((Character) operStack.peek())){
num1 = (int) numStack.pop();
num2 = (int) numStack.pop();
oper = (char) operStack.pop();
res = operStack.cal(num1, num2, oper);
numStack.push(res);
operStack.push(ch);
}else {
// 如果优先级大于, 直接压入栈中
operStack.push(ch);
}
}
}else{
// 不是符号
// 数字直接压入栈中
numStack.push(ch - 48);
}
if(index >= exp.length()){
break ;
}
}
while (!operStack.isEmpty()){
num1 = (int) numStack.pop();
num2 = (int) numStack.pop();
oper = (char) operStack.pop();
res = operStack.cal(num1, num2, oper);
numStack.push(res);
}
System.out.println(numStack.pop());
}
上面存在问题: 连续使用两个减: 3-6*2-2 期望:-11 实际: -7
原因: 表达式分解完后,对剩余数据运算时, 顺序必须从符号栈底向上运算
最后处理数栈、符号栈剩余数据时修改了下:
ArrayStack t1 = new ArrayStack(10);
ArrayStack t2 = new ArrayStack(10);
while(!numStack.isEmpty()){
t1.push(numStack.pop()); // 相当于从原来的栈底开始运算
}
while (!operStack.isEmpty()){
t2.push(operStack.pop()); // 从栈底开始运算
}
while (!t2.isEmpty()){
num1 = (int) t1.pop(); // 取两个数
num2 = (int) t1.pop();
oper = (char) t2.pop(); // 取一个符号
res = operStack.cal(num2, num1, oper);
t1.push(res);
}
System.out.println(t1.pop());
多位数问题: 根据上面的计算一位数的代码
只要修改 判断分解出来的是 数字 还是 符号 的 数字那块逻辑
思路:
- 定义 String keepNum = “”; // 用于拼接多位数的.
- 进行数字拼接
- 继续判断下一位是否为数字
3.1 是数字: 继续拼接,判断下一位…
3.2 不是数字: 结束循环, 注意下标问题 !- 最后将 keepNum 重置 !
else{
// 不是符号,但是不能直接进入数栈
keepNum += ch;
while (index < exp.length()){
ch = exp.charAt(index++); // 有安全隐患
if(!numStack.isOper(ch)){
keepNum += ch;
}else {
// 此时判断出符号了,再减1回到这个符号交给上面取判断
index--;
break ;
}
// 防止越界
}
// 压入数栈
numStack.push(Integer.parseInt(keepNum));
// 记得重置 keepNum
keepNum = "";
}