方法1
先用栈s1将中缀表达式转换成后缀表达式,然后用栈2求后缀表达式的结构;
一个错误的代码:
#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<unordered_map>
#include<cstring>
using namespace std;
stack<char> s1;
stack<int> s2;//用来计算后缀表达式的辅助栈
string suffix_exp;//存放后缀表达式
unordered_map<char,int> priority={
{'+',1},
{'-',1},
{'*',2},
{'/',2}
};
void expression_trans(){//中缀表达式转成后缀表达式
string exp;
cin>>exp;
for(int i=0;i<exp.size();i++){
if(exp[i]>='0'&&exp[i]<='9'){//如果是数字直接加入后缀表达式
suffix_exp.push_back(exp[i]);
}
else if(exp[i]=='('){//左括号直接入栈
suffix_exp.push_back(' ');
s1.push(exp[i]);
}
else if(exp[i]==')'){
while(!s1.empty() &&s1.top()!='('){
suffix_exp.push_back(s1.top());
s1.pop();
}
if(!s1.empty() && s1.top()=='('){ // 同时弹出左括号
s1.pop();
}
}
else{
while(!s1.empty()&&s1.top()!='('&&priority[s1.top()]>=priority[exp[i]]){
suffix_exp.push_back(s1.top());
s1.pop();
}
suffix_exp.push_back(' ');
s1.push(exp[i]);
}
}
while(!s1.empty()){
suffix_exp.push_back(s1.top());
s1.pop();
}
}
void compute_exp(){
for(int i=0;i<suffix_exp.size();i++){//从前往后扫描后缀表达式
if(isdigit(suffix_exp[i])){
//cout<<suffix_exp[i];
s2.push(suffix_exp[i]-'0');
// cout<<s2.top()<<endl;
}
else if(suffix_exp[i]=='+'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(a+b);
}
else if(suffix_exp[i]=='-'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(b-a);
}
else if(suffix_exp[i]=='*'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(a*b);
}
else if(suffix_exp[i]=='/'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(b/a);
}
}
}
int main(){
expression_trans();
compute_exp();
//cout<<s2.top();
cout<<suffix_exp;
}
修改了一下
第一次想着修改compute函数,发现有点麻烦,最后直接在trans函数修改,简单了很多,也成功的修改了。所以这告诉我解决问题的办法不止一个,可以多尝试几条路!
成功AC的代码:
#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<unordered_map>
#include<cstring>
using namespace std;
stack<char> s1;
stack<int> s2;//用来计算后缀表达式的辅助栈
string suffix_exp;//存放后缀表达式
unordered_map<char,int> priority={
{'+',1},
{'-',1},
{'*',2},
{'/',2}
};
void expression_trans(){//中缀表达式转成后缀表达式
string exp;
cin>>exp;
for(int i=0;i<exp.size();i++){
if(exp[i]>='0'&&exp[i]<='9'){//如果是数字直接加入后缀表达式
while(exp[i]>='0'&&exp[i]<='9')
{
suffix_exp.push_back(exp[i]);
i++;
}
i--;
suffix_exp.push_back(' ');
}
else if(exp[i]=='('){//左括号直接入栈
s1.push(exp[i]);
}
else if(exp[i]==')'){
while(!s1.empty() &&s1.top()!='('){
suffix_exp.push_back(s1.top());
suffix_exp.push_back(' ');
s1.pop();
}
if(!s1.empty() && s1.top()=='('){ // 同时弹出左括号
s1.pop();
}
}
else{
while(!s1.empty()&&s1.top()!='('&&priority[s1.top()]>=priority[exp[i]]){
suffix_exp.push_back(s1.top());
suffix_exp.push_back(' ');
s1.pop();
}
s1.push(exp[i]);
}
}
while(!s1.empty()){
suffix_exp.push_back(s1.top());
suffix_exp.push_back(' ');
s1.pop();
}
}
void compute_exp(){
for(int i=0;i<(suffix_exp.size()-1);i++){//从前往后扫描后缀表达式
if(suffix_exp[i]==' '){
continue;
}
if(isdigit(suffix_exp[i])){
string num_str;
while(suffix_exp[i]>='0'&&suffix_exp[i]<='9'){
num_str.push_back(suffix_exp[i]);
i++;
}
s2.push(stoi(num_str));
}
else if(suffix_exp[i]=='+'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(a+b);
}
else if(suffix_exp[i]=='-'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(b-a);
}
else if(suffix_exp[i]=='*'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(a*b);
}
else if(suffix_exp[i]=='/'){
int a=s2.top();
s2.pop();
int b=s2.top();
s2.pop();
s2.push(b/a);
}
}
}
int main(){
expression_trans();
compute_exp();
cout<<s2.top();
}
错误原因和错误:
- 没分清楚char的运算符和int的操作数,导致只能处理一位数的操作数
- 每次压入一个操作符入栈时,后缀表达式接一个空格作为分隔
- string类型不能用exp[i].isdigit(),用isdigit(exp[i])
- string可以用push_back();
- 调用函数经常忘记括号();
方法2
#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<unordered_map>
#include<cstring>
using namespace std;
stack<char> op;
stack<int> num;//用来计算后缀表达式的辅助栈
unordered_map<char,int> priority={
{'+',1},
{'-',1},
{'*',2},
{'/',2}
};
void eval(){
int a,b;
a=num.top();
num.pop();
b=num.top();
num.pop();
char c=op.top();
op.pop();
if(c=='+'){
num.push(a+b);
}
else if(c=='-'){
num.push(b-a);
}
else if(c=='*'){
num.push(a*b);
}
else if(c=='/'){
num.push(b/a);
}
}
int main(){
string exp;
cin>>exp;
for(int i=0;i<exp.size();i++){
if(isdigit(exp[i])){
string num_str;
while(isdigit(exp[i])){
num_str.push_back(exp[i]);
i++;
}
i--;
num.push(stoi(num_str));
}
else if(exp[i]=='('){
op.push(exp[i]);
}
else if(exp[i]==')'){
while(op.top()!='('){
eval();
}
op.pop();
}
else{
while(!op.empty()&&op.top()!='('&&priority[op.top()]>=priority[exp[i]]){
eval();
}
op.push(exp[i]);
}
}
while(!op.empty()){
eval();
}
cout<<num.top();
return 0;
}
很清晰的思路