题意
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
- 数据保证给定的表达式合法。
- 题目保证符号
- 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
- 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过 $2^{31}-1$。
- 题目中的整除是指向 $0$ 取整，也就是说对于大于 $0$ 的结果向下取整，例如 $5/3=1$，对于小于 $0$ 的结果向上取整，例如 $5/(1-4) = -1$。
- C++和Java中的整除默认是向零取整；Python中的整除
//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。
输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过 $10^5$。
输入样例：
(2+2)*(1+1)
输出样例：
8
思想
表达式求值：
- 如果当前元素是数字：压入
- 如果当前元素是
(：压入
- 如果当前元素是
)：操作到(
- 如果当前元素是
+-*/：从右往左操作到(或者 栈顶优先级$<$当前元素的优先级
操作完运算符栈后，数栈栈顶为答案。
Code
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
unordered_map<char, int> h{{'+','1'}, {'-','1'}, {'*','2'}, {'/','2'}};
stack<char> op;
stack<int> nums;
void eval()
{
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char c = op.top();
op.pop();
int x;
if(c == '+') x = a + b;
if(c == '-') x = a - b;
if(c == '*') x = a * b;
if(c == '/') x = a / b;
nums.push(x);
}
int main()
{
string str;
cin >> str;
for(int i = 0; i < str.size(); i ++ )
{
if(isdigit(str[i]))
{
int j = i, sum = 0;
while(j < str.size() && isdigit(str[j]))
{
sum = sum * 10 + str[j] - '0';
j ++ ;
}
nums.push(sum);
i = j - 1;
}
else if(str[i] == '(') op.push(str[i]);
else if(str[i] == ')')
{
while(op.top() != '(')
{
eval();
}
op.pop();
}
else
{
while(op.size() && h[op.top()] >= h[str[i]])
{
eval();
}
op.push(str[i]);
}
}
while(op.size()) eval();
cout << nums.top() << endl;
return 0;
}
|
中缀表达式转后缀表达式
中缀表达式：(2+2)x(1+1)+3
后缀表达式（无需括号）：22+11+x3+
代码转换方式：将中缀表达式中的数栈直接删除，遇见数字直接输出即可。
思想转化方法：将中缀表达式树画出来，如图。
.
$A-(B+C/D)*E+F$
.
.
最后得到的表达式树
前序遍历就是前缀表达式
中序遍历就是中缀表达式
后序遍历就是后缀表达式
Code
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
unordered_map<char, int> h{{'+','1'}, {'-','1'}, {'*','2'}, {'/','2'}};
stack<char> op;
void eval()
{
cout << op.top() << " ";
op.pop();
}
int main()
{
string str;
cin >> str;
for(int i = 0; i < str.size(); i ++ )
{
if(isdigit(str[i]))
{
int j = i, sum = 0;
while(j < str.size() && isdigit(str[j]))
{
sum = sum * 10 + str[j] - '0';
j ++ ;
}
cout << sum << " ";
i = j - 1;
}
else if(str[i] == '(') op.push(str[i]);
else if(str[i] == ')')
{
while(op.top() != '(')
{
eval();
}
op.pop();
}
else
{
while(op.size() && h[op.top()] >= h[str[i]])
{
eval();
}
op.push(str[i]);
}
}
while(op.size()) eval();
return 0;
}
|
括号匹配
苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。
输入格式
共一行，包含一个由 <,(,{,[,>,),},] 构成的字符串。
输出格式
如果输入的字符串中的括号正确匹配则输出 yes，否则输出 no。
数据范围
输入字符串长度不超过 $10000$。
输入样例：
(){}
输出样例：
yes
Code
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
string str;
stack<char> op;
unordered_map<char, int> mp{{'(', 1}, {')', 1}, {'[', 2}, {']', 2}, {'{', 3}, {'}', 3}, {'<', 4}, {'>', 4}};
int main()
{
cin >> str;
for(int i = 0; i < str.size(); i ++ )
{
if(str[i] == '<' || str[i] == '[' || str[i] == '{' || str[i] == '(') op.push(str[i]);
else
{
if(op.size() == 0) continue;
else if(mp[op.top()] != mp[str[i]])
{
puts("no");
return 0;
}
else
{
op.pop();
}
}
}
if(op.size() == 0) puts("yes");
else puts("no");
return 0;
}
|
