1. 前缀表达式 (波兰表达式)
前缀表达式的运算符位于操作数之前
[举例说明] (3+4)*5-6 对应的前缀表达式就是 - * + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式, 遇到数字时, 将数字压入堆栈, 遇到运算符时, 弹出栈顶的两个数, 用运算符对它们做相应的计算 (栈顶元素 和 次顶元素), 并将结果入栈; 重复上述过程直到表达式最左端, 最后运算得出的值即为表达式的结果
[举例说明] 针对上例的前缀表达式求值步骤如下 (栈顶 ? 次顶):
从右至左扫描, 将 6,5,4,3 压入堆栈
遇到 + 运算符, 因此弹出 3 和 4(3 为栈顶元素, 4 为次顶元素), 计算出 3+4 的值, 得 7, 再将 7 入栈
接下来是 * 运算符, 因此弹出 7 和 5, 计算出 7*5=35, 将 35 入栈
最后是 - 运算符, 计算出 35-6 的值, 即 29, 由此得出最终结果
2. 中缀表达式
中缀表达式就是常见的运算表达式, 如 (3+4)*5-6
中缀表达式的求值是我们人最熟悉的, 但是对计算机来说却不好操作 (08 - 案例就能看的这个问题), 因此, 在计算结果时, 往往会将中缀表达式转成其它表达式来操作 (一般转成后缀表达式)
3. 后缀表达式 (逆波兰表达式)
后缀表达式又称逆波兰表达式, 与前缀表达式相似, 只是运算符位于操作数之后
[举例说明] (3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 -
后缀表达式的计算机求值
从左至右扫描表达式, 遇到数字时, 将数字压入堆栈, 遇到运算符时, 弹出栈顶的两个数, 用运算符对它们做相应的计算 (次顶元素 和 栈顶元素), 并将结果入栈; 重复上述过程直到表达式最右端, 最后运算得出的值即为表达式的结果
[举例说明] 针对上例的前缀表达式求值步骤如下 (次顶 ? 栈顶):
从左至右扫描, 将 3 和 4 压入堆栈
遇到 + 运算符, 因此弹出 4 和 3(4 为栈顶元素, 3 为次顶元素), 计算出 3+4 的值, 得 7, 再将 7 入栈
将 5 入栈;
接下来是 * 运算符, 因此弹出 5 和 7, 计算出 7*5=35, 将 35 入栈
将 6 入栈
最后是 - 运算符, 计算出 35-6 的值, 即 29, 由此得出最终结果
4. 中缀表达式 → 后缀表达式
后缀表达式适合计算式进行运算, 但是人却不太容易写出来, 尤其是表达式很长的情况下. 因此在开发中, 我们需要将 中缀表达式 → 后缀表达式
4.1 具体步骤
4.2 举例
5. 逆波兰计算器
要求
输入一个逆波兰表达式 (后缀表达式), 使用栈 (Stack), 计算其结果
支持小括号和多位数整数 (仅支持对整数的计算)
思路
从左到右遍历逆波兰表达式. 遇到数字就入栈; 遇到运算符就出栈 [栈顶元素] 和 [次顶元素], 用该运算符对其进行运算, 之后再将计算结果压栈
遍历结束后,[栈顶元素] 即为 最终表达式结果
6. 代码实现 (综合 4, 5)
- public class PolandNotaion {
- public static void main(String[] args) {
- String suffixExpression = "(30+4)*5-6";
- List<String> list = parseSuffixExpression(suffixExpression);
- System.out.println("算式结果:" + calculate(list));
- }
- // 将 中缀表达式 (算式) 由 String → List
- public static List<String> toInfixExpressionList(String str) {
- char[] arr = str.toCharArray();
- // 定义 List
- List<String> list = new ArrayList<>();
- // 用于遍历 str
- int i = 0;
- // 用于对多位数的拼接
- String temp = "";
- char c;
- while (i <arr.length) {
- if((c=arr[i]) < 48 || (c=arr[i])> 57) { // c 不是数字
- list.add("" + c);
- i++;
- } else { // c 是数字
- while(i <arr.length && (c=arr[i])>= 48 && (c=arr[i]) <= 57) {
- temp += c;
- i++;
- }
- list.add(temp);
- temp = "";
- }
- /*
- c = arr[i];
- if(c <48 || c> 57) { // c 不是数字
- list.add("" + c);
- } else { // c 是数字
- temp += c;
- if((i+1 != arr.length) && (arr[i+1] <48 || arr[i+1]> 57)) {
- list.add(temp);
- temp = "";
- }
- }
- i++;
- */
- }
- return list;
- }
- // 中缀表达式 List → 后缀表达式 List
- public static List<String> parseSuffixExpression(String infixExpression) {
- // 中缀表达式的字符串 → List
- List<String> infixExpressionList = toInfixExpressionList(infixExpression);
- // 定义 [运算符栈 s1]
- Stack<String> s1 = new Stack<>();
- /*
- * 定义 [存储中间结果的栈 s2]
- * 解释: s2 这个栈, 在整个过程中没有 pop 操作, 而且在末尾还需要逆序输出
- * 不如 直接使用一个 List 来替代 s2 的栈结构
- */
- List<String> s2 = new ArrayList<>();
- // 遍历 infixExpressionList
- for(String item : infixExpressionList) {
- if(item.matches("\\d+")) { // 是数, 加入 s2
- s2.add(item);
- } else if(s1.isEmpty() || item.equals("(")) {
- s1.push(item);
- } else if(item.equals(")")) {
- // 依次弹出 s1 栈顶的运算符, 并压入 s2
- while(!s1.peek().equals("(")) { // 直到遇到 "(" 为止
- s2.add(s1.pop());
- }
- s1.pop(); // 将 "(" 弹出, 即将这对括号丢弃
- } else {
- // 运算符优先级 ≤ 栈顶运算符优先级
- while(s1.size()> 0 && getPriority(item) <= getPriority(s1.peek())) {
- // 将 {栈顶运算符} 弹出并压入 s2 中
- s2.add(s1.pop());
- }
- s1.push(item);
- }
- }
- // 将 s1 中剩余的运算符 依次弹出 并加入 s2
- while(s1.size() != 0)
- s2.add(s1.pop());
- // 依次弹出 s2 中的元素并输出, 结果的逆序即为 中缀表达式对应的后缀表达式
- // 因为 s2 是 List, 所以存放的顺序就是最终后缀表达式的顺序
- return s2;
- }
- // 返回运算符优先级 (拟定为: 优先级使用数字表示, 数字越大, 则优先级越高)
- public static int getPriority(String operation) {
- int val = 0;
- switch (operation) {
- case "+":
- val = 1;
- break;
- case "-":
- val = 1;
- break;
- case "*":
- val = 2;
- break;
- case "/":
- val = 2;
- break;
- default:
- System.out.println("不存在该运算符" + operation);
- break;
- }
- return val;
- }
- // 完成对逆波兰表达式的计算
- public static int calculate(List<String> list) {
- // 创建栈 (仅需 1 个栈即可)
- Stack<String> stack = new Stack<String>();
- // 遍历 list
- for(String item : list)
- // 这里使用 [正则表达式] 来取数
- if(item.matches("\\d+")) { // --> 匹配 多位数
- // 入栈
- stack.push(item);
- } else { // --> 匹配 运算符
- // 弹出 栈顶元素 和 次顶元素, 并通过此次扫描到的运算符进行运算
- int topNum = Integer.parseInt(stack.pop());
- int nextTopNum = Integer.parseInt(stack.pop());
- // 解析运算符 (次顶 ___ 栈顶)
- int result;
- if(item.equals("+"))
- result = nextTopNum + topNum;
- else if(item.equals("-"))
- result = nextTopNum - topNum;
- else if(item.equals("*"))
- result = nextTopNum * topNum;
- else if(item.equals("/"))
- result = nextTopNum / topNum;
- else
- throw new RuntimeException("运算符有误");
- // 将结果再次入栈
- stack.push(result + "");
- }
- return Integer.parseInt(stack.pop());
- }
- }
来源: http://www.bubuko.com/infodetail-3394758.html