LeetCode刷题笔记(Evaluate Reverse Polish Notation)
刚刚又刷了一道题,感觉难度不是很大,下面就和大家分享一下经验吧!
题目如下:
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
题意分析:
计算以逆波兰式表示的算术表达式的值。有效的运算符仅包括+, -, *, /,且每个操作数应该是一个整数或者是一个表达式。
注:①两个整数相除,结果向零取整;
②被给的逆波兰表达式总是有效的。
解答如下:
方法一(堆栈法)
创建一个存放整型变量的栈,用for循环遍历字符串向量,当遇到字符串数字时,先将其转换成整型数字(用stoi函数),然后在压入堆栈;当遇到字符串运算符时,先弹出最后进栈的两个整型数字,然后用字符串运算符对他们进行计算(注意操作数的顺序),再将计算的结果压入栈中。最后,待循环结束后,返回堆栈中的计算结果即可。
class Solution{
public:
int evalRPN( vector<string>& tokens ){
stack<int> stack; //新建堆栈
int a;
int b;
for (int i = 0; i < tokens.size(); i++) { //遍历字符串向量,并进行相关操作
if ( tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") stack.push( stoi(tokens[i]) );
else if( tokens[i] != "+" ) { b = stack.top(); stack.pop(); a = stack.top(); stack.pop(); stack.push(a + b);}
else if( tokens[i] != "-" ) { b = stack.top(); stack.pop(); a = stack.top(); stack.pop(); stack.push(a - b);}
else if( tokens[i] != "*" ) { b = stack.top(); stack.pop(); a = stack.top(); stack.pop(); stack.push(a * b);}
else if( tokens[i] != "/" ) { b = stack.top(); stack.pop(); a = stack.top(); stack.pop(); stack.push(a / b);}
}
return stack.top(); //返回结果
}
};
提交后的结果如下:
方法二(优化方法一)
① 考虑字符串向量长度为1的情况;
② 简化“弹出最后进栈的两个整型数字的操作”
class Solution {
public:
int evalRPN(vector<string> &tokens) {
if ( tokens.size() == 1 ) return stoi(tokens[0]); //优化一
stack<int> stack;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/")
stack.push(stoi(tokens[i]));
else { //优化二
int b = stack.top();
stack.pop();
int a = stack.top();
stack.pop();
if (tokens[i] == "+") stack.push(a + b);
if (tokens[i] == "-") stack.push(a - b);
if (tokens[i] == "*") stack.push(a * b);
if (tokens[i] == "/") stack.push(a / b);
}
}
return stack.top();
}
};
提交后的结果如下:
日积月累,与君共进,增增小结,未完待续。