题目：
先转为前缀表达式，然后对前缀表达式求值
- 需要先对字符去除空格，且对于负号(非减号，即单目运算符)在其前面插入 0 使得变为双目运算符。
- ‘-‘为第一个字符的是单目运算符即负号，前面插入 0
- ‘-‘前面是’(‘的是单目运算符即负号，前面插入 0
- 其他情况下’-‘是双目运算符即减号
- 然后转为前缀表达式，按空格分割各个操作数和操作符。首先创建一个存储符号的栈 opStack，记返回值为
string ret，遍历中缀表达式的每个字符。
- 对于数字，不断加入 ret 直到下一个是非数字，然后 ret 后加一个空格进行分割，表示这是一个操作数
- 对于’(‘，直接加入 opStack
- 对于’)’，弹出 opStack 中的所有双目运算符(‘+’或’-‘或’*‘或’/‘)加入 ret，直到栈顶’(‘，弹出’(‘但不加入 ret
- 对于双目运算符(‘+’或’-‘或’*‘或’/‘)
- 如果栈顶元素也是双目运算符，且当前的双目运算符的优先级小于栈顶优先级，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中
- 其他情况下，把当前双目运算符加入栈中。
- 最后如果 opStack 不为空，则把剩下的元素依次弹出加入 ret
- 最后对后缀表达式求值，注意求值最好用 long，最后转为 int
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <sstream>
using std::stack;
using std::string;
using std::vector;
class Solution {
public:
int getPrecedence(char op)
{
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
}
vector<string> split(const string &s)
{
vector<string> tokens;
std::istringstream iss(s);
string token;
while (iss >> token) {
tokens.push_back(token);
}
return tokens;
}
string conv_suffix_expr(string s)
{
string ret;
stack<char> opStack;
char ch;
int i = 0, n = s.size();
while (i < n) {
ch = s[i];
if (std::isdigit(ch)) {
while (i < n && std::isdigit(s[i])) {
ret += s[i];
i++;
}
ret += " ";
i--;
} else if (ch == '(') {
opStack.push(ch);
} else if (ch == ')') {
while (!opStack.empty() && opStack.top() != '(') {
ret += opStack.top();
ret += " ";
opStack.pop();
}
if (!opStack.empty())
opStack.pop();
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
while (!opStack.empty() &&
getPrecedence(opStack.top()) > 0 &&
getPrecedence(opStack.top()) >= getPrecedence(ch)) {
ret += opStack.top();
ret += " ";
opStack.pop();
}
opStack.push(ch);
}
i++;
}
while (!opStack.empty()) {
ret += opStack.top();
ret += " ";
opStack.pop();
}
return ret;
}
int suffix_expr_cal(string &postfix)
{
vector<string> tokens = split(postfix);
stack<long> st;
long a, b;
for (const string &token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
b = st.top();
st.pop();
a = st.top();
st.pop();
if (token == "+")
st.push(a + b);
else if (token == "-")
st.push(a - b);
else if (token == "*")
st.push(a * b);
else if (token == "/")
st.push(a / b);
} else {
st.push(std::stol(token));
}
}
return (int)st.top();
}
string handleUnaryMinus(const string &s)
{
string clean;
for (char c : s) {
if (c != ' ')
clean += c;
}
string result;
int n = clean.size();
for (int i = 0; i < n; ++i) {
char c = clean[i];
if (c == '-') {
if (i == 0) {
result += "0-";
} else {
char prev = clean[i - 1];
if (prev == '(') {
result += "0-";
} else {
result += '-';
}
}
} else {
result += c;
}
}
return result;
}
int calculate(string s)
{
s = handleUnaryMinus(s);
string postfix = conv_suffix_expr(s);
return suffix_expr_cal(postfix);
}
};
|
只有加减
由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。括号不能忽略，因为虽然”+”和”-“运算优先级相同，但是括号会改变优先级。
变化主要在于没有了双目运算符的优先级判断，即对于原来的”如果栈顶元素也是双目运算符，且当前的双目运算符的优先级小于栈顶优先级，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中”,变为”如果栈顶元素是双目运算符，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中”。
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
| string conv_suffix_expr(string s) {
string ret;
stack<char> opStack;
int i = 0, n = s.size();
while (i < n) {
char ch = s[i];
if (std::isdigit(ch)) {
while (i < n && std::isdigit(s[i])) {
ret += s[i];
i++;
}
ret += " ";
i--;
}eles if (ch == '(') {
opStack.push(ch);
}else if (ch == ')') {
while (!opStack.empty() && opStack.top() != '(') {
ret += opStack.top();
ret += " ";
opStack.pop();
}
if (!opStack.empty()) opStack.pop();
}else if (ch == '+' || ch == '-') {
while (!opStack.empty() &&
opStack.top() != '(' ) {
ret += opStack.top();
ret += " ";
opStack.pop();
}
opStack.push(ch);
}
i++;
}
while (!opStack.empty()) {
ret += opStack.top();
ret += " ";
opStack.pop();
}
return ret;
}
|
DFS 递归
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
| class Solution {
int i = 0;
public int calculate(String s) {
return dfs(s, 1);
}
public int dfs(String s, int positive){
int res = 0;
while(i < s.length()){
char c = s.charAt(i);
if(Character.isDigit(c)){
int num = c - '0';
while(i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))){
num = num * 10 + s.charAt(++i) - '0';
}
res += positive * num;
}else if(c == '+' || c == '-'){
positive = c == '+' ? 1 : -1;
}else if(c == '('){
i++;
res += positive * dfs(s, 1);
}else if(c == ')'){
break;
}
i++;
}
return res;
}
}
|
