时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32M,其他语言64M
链接:https://www.nowcoder.com/questionTerminal/22f9d7dd89374b6c8289e44237c70447
来源:牛客网
计算逆波兰式(后缀表达式)的值
运算符仅包含"+","-","*"和"/",被操作数可能是整数或其他表达式
例如:
["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
思路:
- 计算结果时,stack至少2个数,否则不合法,返回0遇到数字就入栈
- 如果不是操作数,也无法转换为数字,就返回0,这里用try catch结果要合法:
- 如果遍历完成,stack的元素不止1个,说明不合法,返回0
- 当stack元素只有一个的时候,返回结果
来自 @hustZa
来自 @haorlee
使用该容器时需要包含#include<stack>头文件;
定义stack对象的示例代码如下:
stack<int>s1;
stack<string>s2;
stack的基本操作有:
1.入栈:如s.push(x);
2.出栈:如 s.pop().注意:出栈操作只是删除栈顶的元素,并不返回该元素。
3.访问栈顶:如s.top();
4.判断栈空:如s.empty().当栈空时返回true。
5.访问栈中的元素个数,如s.size();
class Solution {
public:
int evalRPN(vector<string> &tokens) {
if(tokens.size() == 0)
return 0;
stack<int> st;
for(int i=0;i<tokens.size();++i) {
string s = tokens[i];
if(s == "+" || s == "-" || s== "*" || s == "/"){
if(st.size() < 2)
return 0;
int num2 = st.top(); st.pop();
int num1 = st.top(); st.pop();
int result = 0;
if(s == "+")
result = num1 + num2;
else if(s == "-")
result = num1 - num2;
else if(s == "*")
result = num1 * num2;
else if(s == "/")
result = num1 / num2;
st.push(result);
}
else{
st.push(atoi(s.c_str()));
}
}
return st.top();
}
};
Author: Frytea
Title: 编程题evaluate-reverse-polish-notati
Link: https://cloud.tencent.com/developer/article/1662777
Copyright: This work by TL-Song is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.