欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

evaluate-reverse-polish-notation

程序员文章站 2022-05-25 16:25:51
题目描述: Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are+,-,*,/. Each operand may be an integer or another ......

题目描述:

Evaluate the value of an arithmetic expression in . 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

解题思路:

  题目考察栈的使用,也是《数据结构与算法分析--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 };