1 题目描述
计算逆波兰式（后缀表达式）的值
运算符仅包含"+","-","*“和”/"，被操作数可能是整数或其他表达式
例如：
[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9? [“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6
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”,"+",“3”,"*"]
输出
9
2 解题思路
2.1 知识补充
2.1.1 逆波兰表达式
逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J?卢卡西维兹(J? Lukasewicz)于1929年首先提出的一种表达式的表示方法 [1] 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。逆波兰表达式_百度百科
2.2 解题思路
- 建立一个操作数栈。
- 顺序遍历逆波兰表达式：
2.1. 当遇到操作数时，将操作数压入操作数栈
2.2. 当遇到操作符时，先弹出一次操作数栈的栈顶元素作为操作数2，再弹出第二次操作数栈的栈顶元素作为操作数1，计算操作数1 操作符 操作数2（例如，操作数1为1，操作数2 为2，操作符为+，则操作数1 操作符 操作数2为1+2等于3），并将结果压入操作数栈。 - 当逆波兰表达式遍历完成时，返回操作数栈的栈顶元素即为数学表达式结果。
3 代码实现
class Solution {
public:/*** * @param tokens string字符串vector * @return int整型*/int evalRPN(vector<string>& tokens) {// write code herestack<int> operands;for(int i = 0; i < tokens.size(); i++){try{operands.push(stoi(tokens[i]));}catch(...){int operand2 = operands.top();operands.pop();int operand1 = operands.top();operands.pop();operands.push(calc(operand1, operand2, tokens[i]));}}return operands.top();}int calc(int operand1, int operand2, string oprt){if(oprt == "+") return operand1 + operand2;if(oprt == "-") return operand1 - operand2;if(oprt == "*") return operand1 * operand2;if(oprt == "/") return operand1 / operand2; // truncatecout<<"OperatorError."<<endl;return -1;}
};
4 运行结果
运行时间：5ms
占用内存：528k