A46328. 中缀表达式的值
填空题
困难
知识点
题目描述
中缀表达式的值
题目描述
人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值。 给定一个中缀表达式，编写程序，利用堆栈的方法，计算表达式的值。
输入
第一行为测试数据的组数N 接下来的N行，每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号，操作数都是正整数，数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。
输出
对每一组测试数据输出一行，为表达式的值
样例输入
3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))
样例输出
43
64
108
提示
注意：运算过程均为整数运算（除法运算'/'即按照C++定义的int除以int的结果，测试数据不会出现除数为0的情况），输出结果也为整数（可能为负）。 中间计算结果可能为负。
参考答案
#include<iostream>
#include<string>
#include<stack>
#include<cstdlib>
#include<sstream>
#include<vector>
using namespace std;
int string_to_int(string a){
stringstream ss;
int s;
ss<<a;
ss>>s;
return s;
}
int judge(string a){
if(a=="+"||a=="-")
return 1;
else if(a=="*"||a=="/")
return 2;
else if(a=="(")
return 3;
else if(a==")")
return -1;
else
return 0;
}
vector<string> chu_shi_hua(string s){//初始化
vector<string>a;
int j,i;
i=0;
while(i<s.size())
{ j=i;
while(j<s.size()&&s.at(j)<='9'&&s.at(j)>='0'){
j++;
}
if(i==j){
a.push_back(s.substr(i,1));
i=i+1;
}
else{
a.push_back(s.substr(i,j-i));
i=j;
}
}
return a;
}
int calculate(vector<string> s){
stack<int> result;
int a,b;
for(int i=0; i<s.size();i++){
if(judge(s[i])==0)
result.push(string_to_int(s[i]));
else{
a=result.top();
result.pop();
b=result.top();
result.pop();
if(s[i]=="+")
result.push(b+a);
if(s[i]=="-")
result.push(b-a);
if(s[i]=="*")
result.push(a*b);
if(s[i]=="/")
result.push(b/a);
}
}
return result.top();
}
vector<string> zhong_hou(vector<string> s){
stack<string> result;
vector<string> save;
for(int i=0; i<s.size();i++){
if(judge(s[i])==0)//遇到数字就直接输出
save.push_back(s[i]);
if(judge(s[i])>0){
if(result.empty())//栈为空则直接压栈
result.push(s[i]);
else{
if(judge(s[i])>judge(result.top()))//操作符优先级比栈顶操作符优先级高
{ result.push(s[i]);
}
else{
while((!result.empty())&&judge(result.top())>=judge(s[i])&&result.top()!="(")//弹栈并输出直到栈为空或遇到优先级更低的操作符 (除了左括号)
{
save.push_back(result.top());
result.pop();
}
result.push(s[i]);
}
}
}
if(judge(s[i])==-1){
while(result.top()!="("){
save.push_back(result.top());
result.pop();
}
result.pop();
}
}
while(!result.empty()){
save.push_back(result.top());
result.pop();
}
return save;
}
int main(){
int n;
string s1;//s1表达式
vector<string> s2,s3;//s2是初始化后的表达式，将多位的数字分出来。s3是后缀表达式
cin>>n;
while(n--){
cin>>s1;
s2=chu_shi_hua(s1);
s3=zhong_hou(s2);
cout<<calculate(s3)<<endl;
}
return 0;
}
上一题
下一题