算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式说明：
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号（），表达式不超过20个字符。
输出格式说明：
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
2+3*(7-4)+8/4 |
2 3 7 4 - * + 8 4 / + |
| 2 |
((2+3)*4-(8+2))/5 |
2 3 + 4 * 8 2 + - 5 / |
| 3 |
1314+25.5*12 |
1314 25.5 12 * + |
| 4 |
-2*(+3) |
-2 3 * |
| 5 |
123 |
123 |
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
stack<char> s;
int Judge(char a)
{
if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)||(a==‘(‘)||(a==‘)‘)) return 1;
return 0;
}
int Judge_(char b,char a)
{
if(b==‘+‘||b==‘-‘)
if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)||(a==‘(‘)) return 1;
return 0;
}
int Judge_jjcc(char a)
{
if((a==‘+‘)||(a==‘-‘)||(a==‘*‘)||(a==‘/‘)) return 1;
return 0;
}
int Judge_jj(char a)
{
if((a==‘+‘)||(a==‘-‘)) return 1;
return 0;
}
int premer(char a,char b)
{
switch(a)
{
case ‘+‘:
{
switch(b)
{
case ‘+‘:return 0;break;
case ‘-‘:return 0;break;
case ‘*‘:return 0;break;
case ‘/‘:return 0;break;
case ‘(‘:return 0;break;
}
}break;
case‘-‘:
{
switch(b)
{
case ‘+‘:return 0;break;
case ‘-‘:return 0;break;
case ‘*‘:return 0;break;
case ‘/‘:return 0;break;
case ‘(‘:return 0;break;
}
}break;
case ‘*‘:
{
switch(b)
{
case ‘+‘:return 1;break;
case ‘-‘:return 1;break;
case ‘*‘:return 0;break;
case ‘/‘:return 0;break;
case ‘(‘:return 0;break;
}
}break;
case‘/‘:
{
switch(b)
{
case ‘+‘:return 1;break;
case ‘-‘:return 1;break;
case ‘*‘:return 0;break;
case ‘/‘:return 0;break;
case ‘(‘:return 0;break;
}
}break;
case‘(‘:
{
switch(b)
{
case ‘+‘:return 0;break;
case ‘-‘:return 0;break;
case ‘*‘:return 0;break;
case ‘/‘:return 0;break;
case ‘(‘:return 0;break;
}
}break;
default:break;
}
}
int main()
{
char a[30];
scanf("%s",a);
int len=strlen(a);
int con_flag=0;
int op_flag=1;
bool first=false;
for(int i=0;i<len;i++)
{
if(Judge(a[i])&&(!(i==0&&Judge_jj(a[i])))&&(!Judge_(a[i],a[i-1]))) //正常符号
{
if(a[i]==‘)‘)
{
while(s.top()!=‘(‘)
{
char temp=s.top();
s.pop();
cout<<" "<<temp;
}
s.pop();
while(!s.empty()&&s.top()!=‘(‘)
{
char temp_t=s.top();
s.pop();
cout<<" "<<temp_t;
}
}
else if(!s.empty()&&(a[i]!=‘(‘))
{
if(premer(s.top(),a[i])) con_flag=1;
else con_flag=0;
while(con_flag)//压入的操作符优先级要大于顶部元素
{
char temp2=s.top();
cout<<" "<<temp2;
s.pop();
if(!s.empty())
{
if(premer(s.top(),a[i])) con_flag=1;
else con_flag=0;
}
else con_flag=0;
}
s.push(a[i]);
}
else s.push(a[i]);
if(first==false&&Judge_jjcc(a[i]))
{
first=true; cout<<" ";
}
}
else if(a[i]==‘+‘||a[i]==‘-‘)//表示数据的正负
{
if(a[i]==‘-‘) op_flag*=-1; //是-号 后面的数字乘以-1；
//否则忽略
first=true;
}
else
{ if(i==0)
{
cout<<a[i];
}
else
{
if(op_flag==-1) {
cout<<‘-‘<<a[i];
op_flag=1;
}
else cout<<a[i];
first=false;//遇到数字
}
}
}
while(!s.empty())
{
cout<<" "<<s.top();
s.pop();
}
//printf("%s",a);
system("pause");
return 0;
}
解题报告：
对于取进来的字符可以分成3种情况
【1】正常操作符 表示运算关系
【2】正负号 表示数据的正负 如+2*（-2） 注意：本题中+号表示数据的正负时不输出 所以只要考虑‘-’的情况
【3】正常数字
【特殊情况】：判断第一个字符，之所以要考虑第一个字符是因为在字符a[i]的情况下判断情况【2】的状态时要查看a[i-1]，如果是第一个字符 i=0，且a[i]==‘+‘或者a[i]==‘-‘归到【2】，如果是数字归到【3】，如果是正常操作符归到【1】。
输出格式考虑：考虑一种特殊情况，1234···连续的数字。思路：第一次碰到【1】正常操作符入队列的时候输出一个空格。每次弹出操作符都先输出一个空格。
原文：http://blog.csdn.net/linsheng9731/article/details/22619447