首页 > 代码库 > [Leetcode] evaluate reverse polish notation 计算逆波兰表达式

[Leetcode] evaluate reverse polish notation 计算逆波兰表达式

2024-10-28 04:04:39   206人阅读

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

题意：求逆波兰表达式的值

思路：首先说明什么是逆波兰表达式操作符紧邻于对应的（最后一个）操作数之后，比如“1 2 +”。

像括号匹配和求逆波兰表达式是栈典型的应用。该题的思路是：将遍历字符串，将数字型字符压入栈中，遇到操作符，从栈中取出操作符计算所需的数位，进行计算，并将计算结果压入栈中，以便参加后续的计算。代码如下：

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string> &tokens) 
 4     {
 5         if(tokens.empty())  return 0;
 6 
 7         int len=tokens.size();
 8         stack<int> stk;
 9         for(int i=0;i<len;++i)
10         {
11             string s=tokens[i];
12             if(s=="+"||s=="-"||s=="*"||s=="/")
13             {
14                 if(stk.size()<2)
15                     return 0;
16                 int num1=stk.top();
17                 stk.pop();
18                 int num2=stk.top();
19                 stk.pop();
20 
21                 int res=0;
22                 if(s=="+")
23                     res=num1+num2;
24                 if(s=="-")
25                     res=num2-num1;
26                 if(s=="*")
27                     res=num2*num1;
28                 if(s=="/")
29                     res=num2/num1;
30                 stk.push(res);
31             }
32             else
33             {
34                 stk.push(atoi(s.c_str()));   //
35             }
36         }    
37         return stk.top();    
38     }
39 };

 

[Leetcode] evaluate reverse polish notation 计算逆波兰表达式


联系
我们