A-A+

# 中缀式变后缀式

2012年09月16日 中缀式变后缀式已关闭评论 阅读 122 次

## 中缀式变后缀式

```2
1.000+2/4=
((1+2)*5+1)/4=```

```1.000 2 4 / + =
1 2 + 5 * 1 + 4 / =```

[cpp]

//中缀转后缀
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int first(char ch)
{
switch(ch)
{
case '+':
case '-':return 1;
case '*':
case '/':return 2;
case '(':
case '@':
default: return 0;
}
}
void change(string &s1,string &s2)
{
stack<char> s;s.push('@');
int i=0;char ch=s1[i];
//cout<<s1<<" "<<ch<<endl;
while(i<s1.size()-1)
{
//cout<<"s2:"<<s2<<endl;
if(ch=='('){s.push(ch);ch=s1[++i];}
else if(ch==')')
{
while(s.top()!='(') {s2+=s.top();s2+=' ';s.pop();}
s.pop();
ch=s1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
char w=s.top();
while(first(w)>=first(ch))
{
s2+=w;s2+=' ';s.pop();
w=s.top();
}
s.push(ch);
ch=s1[++i];
}
else
{
while((ch>='0'&&ch<='9')||ch=='.')
{
s2+=ch;
ch=s1[++i];
}
s2+=' ';
}
}
ch=s.top();s.pop();
while(ch!='@')
{
s2+=ch;s2+=' ';
ch=s.top();
s.pop();
}
s2+='=';
}
int main()
{
string s1,s2;int n;cin>>n;
while(n--)
{
cin>>s1;s2="";
change(s1,s2);
cout<<s2<<endl;
}
return 0;
}
[/cpp]