逆波兰式计算

Love The Way You Lie 2022-08-26 04:47 196阅读 0赞

本题目来源于LeetCode，计算逆波兰式的值，具体如下：

### Evaluate Reverse Polish Notation ###

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

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

Some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
      ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

首先补充一下逆波兰式的知识，如果你已经非常熟悉，请跳过：

后缀表达式也称为**逆波兰式**（Reverse Polish Notation, RPN），更加广为人知一些，和前缀表达式刚好相反，是将操作符号放置于操作数之后，比如`2 + 3 * (5 - 1)`用逆波兰式来表示则是：`2 3 5 1 - * +`。

逆波兰式的计算也是从左往右依次读取，当读到操作符时，将之前的两个操作数做计算，然后替换这两个操作数和操作符，接着读取，重复此步骤。对于这个表达式，读到`5 1 -`，得到`4`，然后读取乘号，取出前面的`3`和上一步的计算结果`4`，并计算，到`12`，接着读取加号`+`，计算`2 12 +`得到`14`，计算结束。

上面这个步骤可以很容易的用栈来实现：

*从左往右依次读取表达式，如果是数字则将该数字压栈，如果是符号，则将之前的两个数字出栈，做计算后，将计算结果压栈，直到表达式读取结束。栈中剩下的一个数就是计算结果。*

逆波兰式看起来像波兰式反过来，比如`5 + 1`的波兰式是`+ 5 1`，逆波兰式为`5 1 +`或者`1 5 +`。也很明显，逆波兰式并不是简单的将波兰式反过来，因为，减法和除法中减数和被减数、除数与被除数是不能交换的，即`- 10 5`和`- 5 10`就完全不一样。（参考：http://zhouliang.pro/2013/08/18/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/）

这样，实现的思路就非常简单了：

维基百科给出的伪代码如下：

![SouthEast][]

下面给出我的AC代码（整个测试代码），如有错误请大家批评指正：

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include <vector>
    using namespace std;
    
    class Solution {
    public:
    	bool isOperand(string& operand) //判断是否是一个操作符
    	{
    		return ( 
    			operand == "+" ||
    			operand == "-" ||
    			operand == "*" ||
    			operand == "/"
    			) ;
    	}
    	int procOperand(int a, int b, string& operand) //对操作符进行处理
    	{
    		if (operand == "+")
    			return a + b ;
    		if (operand == "-")
    			return a - b ;
    		if (operand == "*")
    			return a*b ;
    		if (operand == "/")
    		{
    			if (b == 0) return INT_MAX ;
    			return a / b ;
    		}
    		return 0 ;
    	} ;
    
    	int evalRPN(vector<string> &tokens) {
    		
    		if (tokens.empty()) return 0 ;
    
    		stack<int> numbers ;
    		
    		for (int i = 0; i < tokens.size(); ++ i)
    		{
    			// 如果不是操作符，那么假设是数字（这是一种不负责任的做法，但是作为OJ题目，还是可以通过的）
    			if ( !isOperand(tokens[i]) ) 
    				numbers.push(atoi(tokens[i].c_str())) ;
    			else
    			{
    				int b = numbers.top() ;
    				numbers.pop() ;
    				int a = numbers.top() ;
    				numbers.pop() ;
    				numbers.push(procOperand(a, b, tokens[i])) ; //计算
    			}
    		}
    		return numbers.top() ;
    	} ;
    };
    
    
    int main(int argc, char** argv)
    {
    	Solution s ;
    	vector<string> tokens ;
    	tokens.push_back("-1") ;
    	tokens.push_back("1") ;
    	tokens.push_back("*") ;
    	tokens.push_back("-1") ;
    	tokens.push_back("+") ;
    	cout << s.evalRPN(tokens) << endl ;
    	tokens.clear() ;
    	tokens.push_back("4") ;
    	tokens.push_back("13") ;
    	tokens.push_back("5") ;
    	tokens.push_back("/") ;
    	tokens.push_back("+") ;
    	cout << s.evalRPN(tokens) << endl;
    
    	return 0 ;
    }

[Reverse Polish Notation]: http://en.wikipedia.org/wiki/Reverse_Polish_notation
[SouthEast]: /images/20220824/ca615b9c37464debb1eb5bb5125f7e03.png