逆波兰式

逆波兰式,也叫后缀表达式(将运算符写在操作数之后)!
利用STL栈将中缀表达式转换成后缀表达式
[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];
while(i<s1.size()-1)
{
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]
数据测试:

思路例子:((7-3)*5+6)*2
stack s栈,string s1原串,string s2新串
S栈压入’@’,((直接压入S栈，7写入s2，’-‘ 比'(‘的优先级高直接压栈，3写入s2,)弹出栈中的数据’-‘,弹出(,’+’比'(‘优先级高压栈,6写入s2，）弹出栈元素+,弹出(,’*’比’@’优先级高压栈,2写入s2,弹栈
5+10*5
stack s栈,string s1原串,string s2新串
S栈压入’@’,5写入s2，’+’优先级高于’@’压入,10写入s2,’*’优先级高于’+’压入,5写入s2，弹出’*”+’.