中缀表达式
我们日常使用的表达式:
9 + (3-1) * 3 +10 /2
称之为 中缀表达式,这种表达式比较符合我们人的阅读习惯,但是因为要判断运算符的优先级 相对于计算机而言却比较麻烦 .
逆波兰表达式
计算机更容易接受的是另一种表达式 后缀表达式 后缀表达式是一位波兰逻辑学家提出的，因此也称之为逆波兰表达式 以上面的中缀表达式为例 其对应的后缀表达式为:
9 3 1 - 3 * + 10 2 / +
中缀表达式转后缀表达式
步骤
- 初始化2个栈 分别用来存储运算符 和数字
2.从左至右扫描中缀表达式 遇到数字 push 入数字栈
- 遇到运算符 比较其与符号栈 栈顶运算符的优先级
3.1 如符号栈为空, 或者栈顶运算符为 '(' 则直接将此运算符入符号栈
3.2 若 优先级比符号栈 栈顶运算符 高 也将运算符压入符号栈
3.3 否则 将符号栈栈顶的运算符pop 出来 并放入 数字栈中, 再次转入3.1步骤 与符号栈中新的栈顶运算符相比较
- 遇到括号时
4.1 如果是左括号 ( 直接入符号栈
4.2 如果是右括号 ) 则依次pop 出符号栈中的运算符 push 进数字栈 直到遇到左括号为止 此时这对括号丢弃
- 重复步骤2-4 直到表达式遍历结束
- 将符号栈中剩余的运算符依次入数字栈
- 依次pop 出数字栈中的元素并输出 结果的逆序 即为中缀表达式对应的后缀表达式
代码实现
public static List<String> parseSuffixExpression(List<String> list) {
// 1 . 初始化数栈和符号栈
Stack<String> operStack = new Stack<>();
//注: 在实际操作中 因为数字栈 始终无pop操作 考虑到使用栈最后还需逆序操作 故可直接使用集合/StringBudier等替换 更加方便 且无需逆序
List<String> numList = new ArrayList<>();
for (String str : list) { // 遍历中缀表达式集合
if (str.matches("\\d+")){
// 遇到数字 push 入数字栈
numList.add(str);
}else if (str.equals("(")){
//如果是左括号 ( 直接入符号栈
operStack.push(str);
}else if (str.equals(")")){
while (!operStack.peek().equals("(")){
//如果是右括号 ) 则依次pop 出符号栈中的运算符 push 进数字栈 直到遇到左括号为止 此时这对括号丢弃
numList.add(operStack.pop()) ;
}
operStack.pop(); //最后栈顶留的是括号 --->括号丢弃
}else{
while (operStack.size() != 0 && OperationCom.getValue(str) <= OperationCom.getValue(operStack.peek() )){
// 运算符优先级小于等于栈顶运算符 将符号栈栈顶的运算符pop 出来 并放入 数字栈中, 再次转入4.1步骤 与符号栈中新的栈顶运算符相比较
numList.add(operStack.pop());
}
// 余下一个运算符入符号栈
operStack.push(str);
}
}
//将符号栈中剩余的运算符依次入数字栈
while(operStack.size() != 0) {
numList.add(operStack.pop());
}
return numList;
}
}
/**
* @author cx
* @description 运算符优先级比较
* @param
* @return
**/
class OperationCom{
private static int ADD = 1 ;
private static int SUB = 1 ;
private static int MUL = 2 ;
private static int DIV = 2 ;
public static int getValue(String operate){
int res = 0 ;
if (operate.equals("+")){
res = ADD ;
}else if (operate.equals("-")){
res = SUB ;
}else if (operate.equals("*")){
res = MUL ;
}else if (operate.equals("/")){
res = DIV ;
}else{
System.out.println("非法参数");
}
return res ;
}
}
执行结果
输入>>中缀表达式:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
输出>>转成后缀缀表达式:[1, 2, 3, +, 4, *, +, 5, -]
逆波兰表达式运算
规则
从左到右遍历每个数字和符号 遇到数字就进栈 遇到符合则将栈顶2个数字按照符合进行运算 运算结果进栈 一直获得最终结果
代码实现(简单的整数四则运算,不考虑小数等计算)
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<String>();
for (String item : list) {
if (item.matches("\\d+")) { // 匹配的是多位数
// 入栈
stack.push(item);
} else {
// pop出两个数，并运算， 再入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
//把res 入栈
stack.push("" + res);
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
执行结果
输入>>后缀缀表达式:[1, 2, 3, +, 4, *, +, 5, -]
输出>> 计算结果为 :16
