首页 > > 程序设计 > C/C++ >

evaluate-reverse-polish-notation

2018-07-25 13:00:54来源：博客园阅读 ()

题目描述：

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:

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

解题思路：

　　题目考察栈的使用，Reverse Polish Notation也是《数据结构与算法分析--C语言描述》一书讲解栈时所举例子之一。

　　计算逆波兰表达式时，先定义一个栈对象stack，遍历给定的表达式，遇到数字时将其push进stack中，遇到运算符时，从stack中pop出两个操作数。

　　根据操作符进行相应计算后，将结果push进stack中。

　　最终stack中应该只有一个元素，即表达式的计算结果。

代码：

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string> &tokens) {
 4         stack <int> nums;
 5         for (auto token : tokens) {
 6             if (token == "+" || token == "-" || token == "*" || token == "/") {
 7                 int tmp1 = nums.top();
 8                 nums.pop();
 9                 int tmp2 = nums.top();
10                 nums.pop();
11                 nums.push(cal(tmp2,tmp1,token));
12             } else {
13                 nums.push(stoi(token));
14             }
15         }
16         return nums.top();
17     }
18     
19     int cal(int a, int b, const string& token) {
20         if (token == "+")
21             return a+b;
22         else if (token == "-")
23             return a-b;
24         else if (token == "*")
25             return a*b;
26         else
27             return a/b;
28     }
29 };