150. 逆波兰表达式求值#
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((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提示：
1 <= tokens.length <= 10^4tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。- 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
栈#
思路，给定逆波兰表达式字符串容器，直接使用栈的方法解决问题。
- 遇到数字字符串直接入栈。
- 遇到操作符字符串，先弹出右操作数，再弹出左操作数，将执行结果入栈。
第一次写的代码：
class Solution {
public:
bool isOperator(const string& s) {
return s == "+" || s == "-" || s == "*" || s == "/";
}
int strToint(const string& s) {
int sum = 0;
int len = s[0] == '-' ? s.size() - 1 : s.size();
/* bug 在 size() 接口，size() 返回类型 size_t 为 unsigned int 类型 */
// for (int i = s.size() - 1, j = 1; i > s.size() - len - 1; --i, j *= 10) {
// sum += (s[i] - '0') * j;
// }
for (int i = (int)s.size() - 1, j = 1; i > (int)s.size() - len - 1; --i, j *= 10) {
// signed integer overflow: 147483648 + 2000000000 cannot be represented in type 'int'
sum += (s[i] - '0') * j;
}
return len == s.size() ? sum : -sum;
}
string intTostr(int num) {
string res;
while (num) {
res.push_back(num % 10 + 48);
num /= 10;
}
reverse(res.begin(), res.end());
return res;
// return to_string(num);
}
string operationTwoNum(const string& oper, const string& str1, const string& str2) {
if (oper == "+") {
return intTostr(strToint(str1) + strToint(str2));
}
else if (oper == "-") {
return intTostr(strToint(str1) - strToint(str2));
}
else if (oper == "*") {
return intTostr(strToint(str1) * strToint(str2));
}
else {
return intTostr(strToint(str1) / strToint(str2));
}
}
int evalRPN(vector<string>& tokens) {
stack<string> strStack;
for (auto& s : tokens) {
if (isOperator(s)) {
// 弹出右操作数
string rightStr = strStack.top();
strStack.pop();
// 弹出左操作数
string leftStr = strStack.top();
strStack.pop();
// 结果入栈
strStack.push(operationTwoNum(s, leftStr, rightStr));
}
else {
strStack.push(s);
}
}
return strToint(strStack.top());
}
};
上面代码写的有很多问题，其中最主要的问题就是溢出问题。
接口函数 size () 返回容器长度，其返回类型是 size_t（unsigned int）当 size () == 0 的时候对其进行减 1 操作就会溢出。
第二次思路
- 创建
long long类型的栈。 - 遇到的字符串不是操作符，就将其转化为
long long类型入栈，这样栈中就全是数而不是字符串，最后在弹出的时候就不需进行处理。 - 遇到的字符串是操作符，就先弹出右操作数，再弹出左操作数，对其进行操作后重新入栈。
- 最后栈顶就是运算结果。
class Solution {
public:
long long strTolonglong(const string& s) {
long long sum = 0; // 转化结果
// int count = s[0] == "-" ? (int)s.size() - 1 : (int)s.size();
int leftMostSub = s[0] == '-' ? 0 : - 1; // 避免溢出问题
for (int i = (int)s.size() - 1, j = 1; i > leftMostSub; --i, j *= 10) {
sum += (s[i] - '0') * j;
}
return leftMostSub ? sum : -sum;
// return stoll(s); // 也可以直接调用库函数
}
int evalRPN(vector<string>& tokens) {
stack<long long> llStack;
for (auto& s : tokens) {
if (s == "+" || s == "-" || s == "*" || s == "/") {
// 先弹出右操作数
long long right = llStack.top();
llStack.pop();
// 在弹出左操作数
long long left = llStack.top();
llStack.pop();
if (s == "+") {
llStack.push(left + right);
}
if (s == "-") {
llStack.push(left - right);
}
if (s == "*") {
llStack.push(left * right);
}
if (s == "/") {
llStack.push(left / right);
}
}
else {
llStack.push(strTolonglong(s));
}
}
return llStack.top();
}
};