一. 什么是后缀表达式
例如: a + b * c + ( d * e + f ) * g , 这是日常中我们看到的简单计算表达式, 这就是一个中缀表达式.
哪什么是后缀表达式呢? 上面这个中缀表达式又该如何转换成后缀表达式呢?
- 将中缀表达式按照运算规则加上括号
- 将括号内的运算符号放在对应括号外面
- 去掉所有的括号
例如上面的中缀表达式 a + b * c + ( d * e + f ) * g
- 将中缀表达式按照运算规则加上括号
( ( a + ( b * c ) ) + ( ( ( d * e ) + f ) * g ) ) - 将括号内的运算符号放在对应括号外面
( ( a ( b c ) * ) + ( ( ( d e ) * f ) + g ) * ) + - 去掉所有的括号
a b c * + d e f + g * +
通过上面三步转换, 就让中缀表达式转为了后缀表达式, 最终的结果就是后缀表达式, 也叫做逆波兰式
二. 逆波兰式的使用
知道了如何变为一个逆波兰式, 也就是后缀表达式, 那么 怎么实现他呢? 例如很多带计算器功能的软件中, 用户输入的都是一个中序表达式, 计算机是通过后缀表达式来计算的, 因此如何用代码实现后缀表达式就至关 重要了.
用栈来模拟实现后缀表达式的计算结果 :
- 遍历后缀表达式中非操作符( + - * / ) 放入压栈
- 遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数
- 弹出的栈顶元素计算后重新压栈
- 直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果
- 遍历后缀表达式中非操作符( + - * / ) 放入压栈
此时遇到的 a b c 均为非操作符, 因此全部压栈, 直至遇到第一个操作符
- 遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数
此时遇到了操作符 , **因此弹出栈顶元素 c 作为右操作数, 弹出第二个栈顶元素 b 作为左操作数
那么, 为什么弹出的第一个栈顶元素时右操作数, 而不是左操作数呢 ?
** 运算法则中, 加减乘除的优先级不同, 如果弹出得第一个元素为左操作数, 可能会因为运算法则的优先级, 导致最终结果错误
例如 :
计算表达式 : a + b * c , a = 1, b = 2, c = 3 , 此时无论 左操作数是 b 还是 c 对于当前表达式都不会影响结果
当 变成 a + b - c 时, a = 1, b = 2, c = 3, b - c 中左操作数如果是 c 右操作数是 b 那么 b - c 就是正数; 同样 左操作数如果是 b 右操作数如果是 c 那么 b - c 就是负数, 会影响后面的计算结果
- 弹出的栈顶元素计算后重新压栈
将出栈后的左操作数和右操作数计算后的结果重新入栈
- 直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果
直至后缀表达式全部遍历完, 最后计算结果保存在栈顶中
三. LeetCode 逆波兰式练习
了解逆波兰表达式如何来的以后, 就可以上力扣去挑战一下啦
leetCode - 逆波兰表达式(点击即可跳转)
根据上面的逆波兰表达式的实现, 可以写出如下代码 :
class Solution { // 需要注意的是, 该题中是字符串数组 public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); // 1. 遍历字符串数组判断该字符是否为操作符 for(String s : tokens) { if(!isOperator(s)) { // 2. 如果不是操作符, 当前元素就压栈 stack.push(Integer.parseInt(s)); }else { // 3. 如果是操作符, 弹出栈顶元素, 第一个为右操作数, 第二个为左操作数 int num2 = stack.pop(); // num2 始终为右操作数 int num1 = stack.pop(); // num1 始终为左操作数 // 4. 计算完成后的结果进行压栈 switch(s) { case "+" : stack.push(num1 + num2); break; case "-" : stack.push(num1 - num2); break; case "*" : stack.push(num1 * num2); break; case "/" : stack.push(num1 / num2); break; } } } // 5. 遍历结束后, 弹出栈顶元素即为所求结果 return stack.pop(); } // 判断是否为操作符 private boolean isOperator(String s) { if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) { return true; } return false; } }
逆波兰表达式学会了, 就可以根据中序表达式简单的实现一个模拟计算器的功能啦, 可以试一试
