算术表达式的转换

题目描述

小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。    因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。

输入

 输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）

输出

 输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

+*ab*-c/def a*b+c-d/e*f ab*cde/-f*+

提示

前缀式的优先级为大于；

后缀式为大于等于；

<span style="font-size:18px;color:#009900;">#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <stack> using namespace std; char str[1000000],str2[1000000]; int n; /*前缀式*/ void per(char str[],int n) { stack<char>S1; char ch; int i,j=0; for(i=n-2;i>=0;i--) { if(str[i]>='a'&&str[i]<='z') str2[j++]=str[i]; else if(!S1.empty()) { if(str[i]=='*'||str[i]=='/') { S1.push(str[i]); } else if(str[i]=='+'||str[i]=='-') { ch=S1.top(); if(ch=='*'||ch=='/') { str2[j++]=ch; S1.pop(); } S1.push(str[i]); } else if(str[i]==')') S1.push(str[i]); else { while(!S1.empty()) { ch=S1.top(); if(ch==')') { S1.pop(); break; } else { str2[j++]=ch; S1.pop(); } } } } else S1.push(str[i]); } while(!S1.empty()) { ch=S1.top(); str2[j++]=ch; S1.pop(); } int m=strlen(str2); for(i=m-1;i>=0;i--) printf("%c",str2[i]); } /*中缀式*/ void ino(char str[],int n) { int i; for(i=0;i<n;i++) { if(str[i]=='#') break; if(str[i]!='('&&str[i]!=')') printf("%c",str[i]); } } /*后缀式*/ void past(char str[],int n) { stack<char>S2; char ch; int i; for(i=0;i<n;i++) { if(str[i]=='#') break; if(str[i]>='a'&&str[i]<='z') printf("%c",str[i]); else if(!S2.empty()) { if(str[i]=='+'||str[i]=='-') { ch=S2.top(); if(ch!='(') { printf("%c",ch); S2.pop(); } S2.push(str[i]); } else if(str[i]=='*'||str[i]=='/') { ch=S2.top(); if(ch=='*'||ch=='/'||ch==')') { printf("%c",ch); S2.pop(); } S2.push(str[i]); } else if(str[i]=='(') S2.push(str[i]); else { while(!S2.empty()) { ch=S2.top(); if(ch=='(') { S2.pop(); break; } else { printf("%c",ch); S2.pop(); } } } } else S2.push(str[i]); } while(!S2.empty()) { ch=S2.top(); printf("%c",ch); S2.pop(); } } int main() { scanf("%s",str); n=strlen(str); per(str,n); printf("\n"); ino(str,n); printf("\n"); past(str,n);</span> return 0; }