2. evaluate-reverse-polish-notation 后缀表达式的求解

拼搏现实的明天。 2022-06-06 06:35 157阅读 0赞

## 题目描述 ##

Evaluate the value of an arithmetic expression in [ Reverse Polish Notation][Reverse Polish Notation].

Valid operators are+,-,\*,/. Each operand may be an integer or another expression

给定一个后缀表达式（逆波兰式），求解答案

## 题目解析 ##

这个题基本没有难度，重点就需要将**后缀表达式**弄清楚。

后缀表达式定义：

一个 [表达式][Link 1]E的后缀形式可以如下定义：

（1）如果E是一个变量或 [常量][Link 2]，则E的 [后缀式][Link 3]是E本身。

（2）如果E是E1 op E2形式的表达式，这里op是如何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式。

（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。

如：我们平时写a+b，这是 [中缀表达式][Link 4]，写成 [后缀表达式][Link 5]就是：ab+

(a+b)\*c-(a+b)/e的后缀表达式为：

(a+b)\*c-(a+b)/e

→((a+b)\*c)((a+b)/e)-

→((a+b)c\*)((a+b)e/)-

→(ab+c\*)(ab+e/)-

→ab+c\*ab+e/-

为什么要引进后缀表达式：

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序[表达式][Link 1]转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

后缀表达式的计算：

将一个普通的中序 [表达式][Link 1]转换为 [逆波兰表达式][Link 6]的一般算法是：

首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符\#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非\#不可。从中缀式的左端开始取字符，逐序进行如下步骤：

（1）若取出的字符是 [操作数][Link 7]，则分析出完整的运算数，该操作数直接送入S2栈

（2）若取出的字符是 [运算符][Link 8]，则将该运算符与S1栈栈顶元素比较，如果该 [运算符优先级][Link 9]大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。

（3）若取出的字符是“（”，则直接送入S1栈顶。

（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个 [出栈][Link 10]，依次送入S2栈，此时抛弃“（”。

（5）重复上面的1~4步，直至处理完所有的输入字符

（6）若取出的字符是“\#”，则将S1栈内所有运算符（不包括“\#”），逐个出栈，依次送入S2栈。

完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！

代码如下：

bool isOperator(string a)
        {
            if (1 == a.size() && 
                (('+' == a[0]) || ('-' == a[0]) || ('*' == a[0]) || ('/' == a[0])) )
            {
                return true;
            }
            else
                return false;
        }
        
        int calculate(char operate, int tmp1, int tmp2)
        {
            int res = 0;
            
            switch (operate)
            {
                case '+':
                    res = tmp2 + tmp1;
                    break;
                case '-':
                    res = tmp2 - tmp1;
                    break;
                case '*':
                    res = tmp2 * tmp1;
                    break;
                case '/':
                    res = tmp2 / tmp1;
                    break;
                default:
                    break;
            }
            return res;
        }
        
        int evalRPN(vector<string> &tokens) 
        {
            stack<int> num;
            int tmp1, tmp2, tmpres;
            
            for (int i = 0 ; i < tokens.size(); i++)
            {
                if (isOperator(tokens[i]))
                {
                    if (num.size() < 2) return 0;
                    
                    tmp1 = num.top();
                    num.pop();
                    tmp2 = num.top();
                    num.pop();
                    
                    tmpres = calculate(tokens[i][0], tmp1, tmp2);
                    
                    num.push(tmpres);
                }
                else
                {
                    num.push(stoi(tokens[i]));
                }
            }
            
            return 1 == num.size() ? num.top() : 0;
        }

[Reverse Polish Notation]: http://en.wikipedia.org/wiki/Reverse_Polish_notation
[Link 1]: https://baike.baidu.com/item/%E8%A1%A8%E8%BE%BE%E5%BC%8F
[Link 2]: https://baike.baidu.com/item/%E5%B8%B8%E9%87%8F
[Link 3]: https://baike.baidu.com/item/%E5%90%8E%E7%BC%80%E5%BC%8F
[Link 4]: https://baike.baidu.com/item/%E4%B8%AD%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F
[Link 5]: https://baike.baidu.com/item/%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F
[Link 6]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F
[Link 7]: https://baike.baidu.com/item/%E6%93%8D%E4%BD%9C%E6%95%B0
[Link 8]: https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6
[Link 9]: https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7
[Link 10]: https://baike.baidu.com/item/%E5%87%BA%E6%A0%88