题目描述：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
数据范围：
- $1 \le s.length \le 3 \times 10^5$
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成s 表示一个有效的表达式- ‘+’ 不能用作一元运算(例如， “+1” 和
"+(2 + 3)" 无效) - ‘-‘ 可以用作一元运算(即 “-1” 和
"-(2 + 3)" 是有效的) - 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
题解：
使用双栈，类似中缀表达式求值。对于一元运算符 -，可以先在前面加一个 $0$ 。
- 如果开头就是
-，前面加 0。 - 如果
( 后面是 -，也需要前面加 0。
括号不能放到优先级列表中去。
每次加入操作符时，判断当前栈顶的优先级是否大于等于当前操作符，是的话就先运算。当然不能遇到 (。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
stack<char> op;
stack<int> nums;
int level(char ch)
{
switch (ch)
{
case '#':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}
int cal(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 -1;
}
int calculate(string s)
{
string ss;
for (auto &x : s)
{
if (x != ' ')
ss += x;
}
s = ss;
s += '#';
int tmp = 0;
for (int i = 0; i < s.length(); ++i)
{
if (s[i] == '-' && (i == 0 || s[i - 1] == '('))
{
nums.push(0);
op.push('-');
continue;
}
if (isdigit(s[i]))
{
tmp = tmp * 10 + (s[i] - '0');
if (!isdigit(s[i + 1]))
{
nums.push(tmp);
tmp = 0;
}
}
else if (s[i] == ')')
{
while (op.top() != '(')
{
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char type = op.top();
op.pop();
nums.push(cal(a, b, type));
}
op.pop();
}
else
{
if (s[i] == '(')
{
op.push(s[i]);
continue;
}
while (op.size() && op.top() != '(' && level(op.top()) >= level(s[i]))
{
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char type = op.top();
op.pop();
nums.push(cal(a, b, type));
}
op.push(s[i]);
}
}
return nums.top();
}
};
|