描述
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣s∣≤1000≤∣s∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度： O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入："1+2"
返回值：3
示例2
输入："(2*(3-4))*5"
返回值：-10
示例3
输入："3+2*3*4-1"
返回值：26
一、使用逆波兰表达式转化法
在前面的栈的使用中，我使用了栈进行逆波兰表达式求值操作，并在其中补充了将中缀表达式转化为逆波兰表达式（后缀表达式）的操作。现在进行回忆。
（一）中缀表达式转化为逆波兰表达式
// 将字符串拆分为 token
vector<string> tokenize(const string& s) {
vector<string> tokens;
string currentToken;
for (char c : s) {
if (isdigit(c) || c == '.') {
// 如果是数字或小数点，则添加到当前 token
currentToken += c;
} else if (c == ' ') {
// 如果是空格，则跳过
continue;
} else {
// 如果是操作符或其他字符，则将当前 token 添加到 tokens 并清空
if (!currentToken.empty()) {
tokens.push_back(currentToken);
currentToken.clear();
}
// 将操作符或其他字符作为一个 token
tokens.push_back(string(1, c));
}
}
// 处理最后一个 token
if (!currentToken.empty()) {
tokens.push_back(currentToken);
}
return tokens;
}
// 将中缀表达式转换为后缀表达式
vector<string> infixToPostfix(const string& s) {
stack<string> operators;
vector<string> output;
unordered_map<string, int> precedence = {{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}};
vector<string> tokens = tokenize(s);
for (const auto& token : tokens) {
if (isdigit(token[0])) {
output.push_back(token);
} else if (token == "(") {
operators.push(token);
} else if (token == ")") {
while (!operators.empty() && operators.top() != "(") {
output.push_back(operators.top());
operators.pop();
}
operators.pop(); // Pop the '('
} else if (precedence.count(token)) { // Check if it's an operator
while (!operators.empty() && precedence[token] <= precedence[operators.top()]) {
output.push_back(operators.top());
operators.pop();
}
operators.push(token);
}
}
while (!operators.empty()) {
output.push_back(operators.top());
operators.pop();
}
return output;
}（二）逆波兰表达式求值
//逆波兰运算
int evalRPN(vector<string>& tokens) {
using namespace std;
// write code here
int l = 0;
int r = 0;
stack<int> stac;
for (string str : tokens) {
if ((str != "+" ) && (str != "-") && (str != "*") && (str != "/")) {
stac.push(stoi(str) );
} else {
int r = stac.top();
stac.pop();
int l = stac.top();
stac.pop();
if (str == "+") {
stac.push(l + r);
} else if (str == "-") {
stac.push(l - r);
} else if (str == "*") {
stac.push(l * r);
} else if (str == "/") {
stac.push(l / r);
}
}
}
return stac.top();
}
（三）调用函数
//中缀表达式转化为逆波兰表达式后进行运算
int solve(string s) {
// write code here
vector<string> tokens = infixToPostfix(s);
return evalRPN(tokens);
}二、直接在栈上进行运算
在实践中我发现，先进行转化在进行计算有些浪费，我认为可以将转化这一步改成计算。
#include <map>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
// 判断优先级
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 计算两个数字的值
int applyOp(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
return 0;
}
int solve(const string& s) {
// write code here
stack<int> values; // 用于存储数字
stack<char> ops; // 用于存储运算符和括号
for (size_t i = 0; i < s.size(); ++i) {
char ch = s[i];
if (isdigit(ch)) {
// 构造完整的数字
int num = 0;
while (i < s.size() && isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
++i;
}
--i; // 因为循环会自动增加 i，所以这里需要减一
values.push(num); // 将数字压入栈
} else if (ch == '(') {
// 左括号直接压入栈
ops.push(ch);
} else if (ch == ')') {
// 遇到右括号时，弹出栈中的元素进行计算，直到遇到左括号
while (!ops.empty() && ops.top() != '(') {
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
if (!ops.empty()) ops.pop(); // 弹出左括号
} else {
// 遇到运算符时，与栈顶运算符比较优先级
while (!ops.empty() && precedence(ops.top()) >= precedence(ch)) {
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(ch); // 将当前运算符压入栈
}
}
// 处理剩余的运算符
while (!ops.empty()) {
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
// 最终结果在栈顶
return values.top();
}
};