中缀表达式转后缀表达式(逆波兰式)

简介: 中缀表达式转后缀表达式(逆波兰式)

一. 什么是后缀表达式



例如: 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 * +
    通过上面三步转换, 就让中缀表达式转为了后缀表达式, 最终的结果就是后缀表达式, 也叫做逆波兰式


二. 逆波兰式的使用



知道了如何变为一个逆波兰式, 也就是后缀表达式, 那么 怎么实现他呢? 例如很多带计算器功能的软件中, 用户输入的都是一个中序表达式, 计算机是通过后缀表达式来计算的, 因此如何用代码实现后缀表达式就至关 重要了.


用栈来模拟实现后缀表达式的计算结果 :

  • 遍历后缀表达式中非操作符( + - * / ) 放入压栈
  • 遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数
  • 弹出的栈顶元素计算后重新压栈
  • 直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果
  • 遍历后缀表达式中非操作符( + - * / ) 放入压栈

b84ed66431a98ffaab82ef9c92fe88ba.png


此时遇到的 a b c 均为非操作符, 因此全部压栈, 直至遇到第一个操作符

  • 遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数

8cce3a3c19fab00931f9d7cd88c56b3f.png


此时遇到了操作符 , **因此弹出栈顶元素 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 就是负数, 会影响后面的计算结果


  • 弹出的栈顶元素计算后重新压栈


7a7dc3fefb52080f3679b20866830a3a.png


将出栈后的左操作数和右操作数计算后的结果重新入栈


  • 直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果

直至后缀表达式全部遍历完, 最后计算结果保存在栈顶中


三. 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;
    }
}


逆波兰表达式学会了, 就可以根据中序表达式简单的实现一个模拟计算器的功能啦, 可以试一试

相关文章
【逆波兰表达式求值】
【逆波兰表达式求值】
|
2月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
54 3
|
2月前
|
存储 C语言
中缀表达式转后缀表达式
本文提供了一个C语言程序,用于将中缀表达式转换为后缀表达式,并计算后缀表达式的结果,包括处理运算符优先级、括号匹配以及基本的四则运算。
47 0
|
7月前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
57 0
|
7月前
彻底大悟!逆波兰表达式求值(150)
彻底大悟!逆波兰表达式求值(150)
|
算法
中缀表达式转后缀表达式(1、2、3) 2021-03-26
中缀表达式转后缀表达式(1、2、3) 2021-03-26
148 0
中缀表达式转后缀表达式(1、2、3) 2021-03-26
后缀表达式
后缀表达式
98 0
|
存储
中缀表达式转化为后缀表达式
中缀表达式转化为后缀表达式
100 0
7-323 逆波兰表达式
7-323 逆波兰表达式
60 0