LeetCode2_Evaluate Reverse Polish Notation评估逆波兰表达式（栈）

佚名 6年前 (2019-05-07) 随笔 1338人围观抢沙发百度已收录

题目：

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

理解这道题首先要理解什么是波兰表达式、什么是逆波兰表达式，这个表达式的意义何在：看参考链接；

参考链接：

Evaluate Reverse Polish Notation：https://www.cnblogs.com/dolphin0520/p/3708587.html

波兰式、逆波兰式与表达式求值：https://blog.csdn.net/linraise/article/details/20459751

思路：遍历这个逆波兰表达式数组，遇到操作数推进操作数的栈s，遇到操作符，将栈s顶两个操作数a和b取出进行操作符运算，将运算结果c放进栈中。

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string> &s) {
 4         stack<int> store;
 5     for(auto x: s)
 6     {
 7         if(x=="+"||x=="-"||x=="*"||x=="/")
 8         {
 9             if(store.size()<2) return 0;
10             int a=store.top();store.pop();
11             int b=store.top();store.pop();
12             int c=0;
13             if(x=="+")
14             c=a+b;
15             else if(x=="-")
16             c=b-a;
17             else if(x=="*")
18             c=b*a;
19             else if(x=="/")
20             c=b/a;
21             store.push(c);
22         }
23         else
24         {
25             store.push(atoi(x.c_str()));
26         }
27  
28      
29     }
30     return store.top();
31     }
32 };