HJ54 表达式求值

112 阅读 0 评论 74 点赞

我是靠谱客的博主坚强万宝路，这篇文章主要介绍HJ54 表达式求值，现在分享给大家，希望可以做个参考。

描述
给定一个字符串描述的算术表达式，计算出结果值。
输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。
数据范围：运算过程中和最终结果均满足

复制代码

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
//运算符优先级比较，括号优先级最高，然后是乘除，再加减
bool priority(const char &a,const char &b){
if(a == '(') return false;
if(((a == '+')||(a == '-'))&&((b == '*')||(b == '/')))
return false;
return true;
}
//根据栈顶运算符弹出两个元素进行运算,并把结果压入数字栈顶
void compute(stack<int> &si,stack<char> &sc){
int b = si.top();
si.pop();
int a = si.top();
si.pop();
//运算符栈顶
char op = sc.top();
sc.pop();
if(op == '+') a = a + b;
else if(op == '-') a = a - b;
else if(op == '*') a = a * b;
else if(op =='/') a = a / b;
//计算结果压入数字栈顶
si.push(a);
}
int getResult(string &str){
stack<int> si;
stack<char> sc;
//给整个表达式加上()
str = "("+str+")";
bool flag = false;
for(int i = 0;i < str.size(); ++i){
//遇到左括号假如到运算栈
if(str[i]=='('){
sc.push('(');
}
//遇到右括号
else if(str[i] == ')'){
//弹出开始计算，直到遇到左括号
while(sc.top() != '('){
compute(si,sc);
}
//弹出左括号
sc.pop();
}
//运算符比较优先级
else if (flag){
while(priority(sc.top(),str[i])){
compute(si,sc);
}
//现阶段符号入栈等待下次计算
sc.push(str[i]);
flag = false;
}
//数字
else{
//开始记录
int j = i;
//正负号
if(str[j] == '+'||str[j] == '-') i++;
while(isdigit(str[i])){
i++;
}
//截取数字部分
string temp = str.substr(j,i - j);
si.push(stoi(temp));
//注意外层i还会+1,所以这里-1
i--;
//数字完了肯定是符号
flag = true;
}
}
//返回栈顶元素，为最终结果。
return si.top();
}
int main() {
string str;
cin >> str;
cout << getResult(str) << endl;
}

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
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
//运算符优先级比较，括号优先级最高，然后是乘除，再加减
bool priority(const char &a,const char &b){
if(a == '(') return false;
if(((a == '+')||(a == '-'))&&((b == '*')||(b == '/')))
return false;
return true;
}
//根据栈顶运算符弹出两个元素进行运算,并把结果压入数字栈顶
void compute(stack<int> &si,stack<char> &sc){
int b = si.top();
si.pop();
int a = si.top();
si.pop();
//运算符栈顶
char op = sc.top();
sc.pop();
if(op == '+') a = a + b;
else if(op == '-') a = a - b;
else if(op == '*') a = a * b;
else if(op =='/') a = a / b;
//计算结果压入数字栈顶
si.push(a);
}
int getResult(string &str){
stack<int> si;
stack<char> sc;
//给整个表达式加上()
str = "("+str+")";
bool flag = false;
for(int i = 0;i < str.size(); ++i){
//遇到左括号假如到运算栈
if(str[i]=='('){
sc.push('(');
}
//遇到右括号
else if(str[i] == ')'){
//弹出开始计算，直到遇到左括号
while(sc.top() != '('){
compute(si,sc);
}
//弹出左括号
sc.pop();
}
//运算符比较优先级
else if (flag){
while(priority(sc.top(),str[i])){
compute(si,sc);
}
//现阶段符号入栈等待下次计算
sc.push(str[i]);
flag = false;
}
//数字
else{
//开始记录
int j = i;
//正负号
if(str[j] == '+'||str[j] == '-') i++;
while(isdigit(str[i])){
i++;
}
//截取数字部分
string temp = str.substr(j,i - j);
si.push(stoi(temp));
//注意外层i还会+1,所以这里-1
i--;
//数字完了肯定是符号
flag = true;
}
}
//返回栈顶元素，为最终结果。
return si.top();
}
int main() {
string str;
cin >> str;
cout << getResult(str) << endl;
}