小c++程序示例,解析并计算算术表达式如 2 + 3 * ( 4–5 ) * ( 6 — ( 7–8 ) ) + 9

这是经典的用堆栈先将 infix expression 转成 postfix expression,接着还是用堆栈来求算结果的算法。很多教科书都省略了例子程序。有的虽然提供了例子程序,却相当冗长。

这里分享的是两个短小精悍的示例,可以分别独立玩味。

这是将 infix expression 转成 postfix expression 的程序:

#include<iostream>
#include<map>
using namespace std;
class S{
private:
int t=0;
char a[50];
public:
void pu(char c){a[t++]=c;}
char po(){return a[--t];}
char pe(){return a[t-1];}
bool em(){return t==0;}
};
int main(){
map<char,int>m={{'+',10},{'-',10},{'*',20},{'/',20}};
S s;
char c;
string x,y="";
while(cin>>x){
if(x=="(")s.pu(x[0]);
else if(x==")")while((c=s.po())!='(')y=y+c+' ';
else if(m.find(x[0])!=m.end()){
while(!s.em()&&m[s.pe()]>=m[x[0]])y=y+s.po()+' ';
s.pu(x[0]);
}else y+=x+' ';
}
while(!s.em())y=y+s.po()+' ';
cout<<y<<endl;
return 0;
}

执行程序,输入的时候用空格分隔每个字符和数。

$ g++ -std=c++11 -Wall gt.cpp && ./a.out
2 + 3 * ( 4 - 5 ) * ( 6 - ( 7 - 8 ) ) + 9
2 3 4 5 - * 6 7 8 - - * + 9 +

下面是计算 postfix expression 的程序。要注意如 “3 4 -” 的出栈顺序,当咱们想要 3–4 时别一不小心变成了 4–3 。除法也有类似的顺序问题。我在这被咬了一口 :D

#include<iostream>
using namespace std;
class S{
private:
int t=0;
int a[50];
public:
void pu(int s){a[t++]=s;}
int po(){return a[--t];}
};
int main(){
S s;
string x;
while(cin>>x){
if(x=="+")s.pu(s.po()+s.po());
else if(x=="-")s.pu(-s.po()+s.po());
else if(x=="*")s.pu(s.po()*s.po());
else if(x=="/"){int x=s.po();s.pu(s.po()/x);}
else s.pu(stoi(x));
}
cout<<s.po()<<endl;
return 0;
}

以下是输入之前的后缀表达式的求值结果:

$ g++ -std=c++11 -Wall gt.cpp && ./a.out
2 3 4 5 - * 6 7 8 - - * + 9 +
-10

--

--

--

1-on-1 tutor of chosen kids

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Golden Thumb

Golden Thumb

1-on-1 tutor of chosen kids

More from Medium

Sixers sneak past the Magic in OT, 116–114

The Mango Tree

Fresh vs. For Sure, Over

How to decide the winner of a raffle based on chat ranking and levels