算术表达式的转换

算术表达式的转换

Time Limit: 1000MS Memory limit: 65536K

题目描述

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

输入

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

输出

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

示例输入

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

示例输出

+*ab*-c/def a*b+c-d/e*f ab*cde/-f*+ （不懂的地方欢迎私信我，我看到的话一定会第一时间给你解答）

#include <stdio.h> #include <string.h> #include <algorithm> #include <stdlib.h> #include <string.h> #include <stack> using namespace std; char a[150]; int len,cnt; void solve(char *n,int f) {//标记变量f来记录是求前缀式还是后缀式； //前缀式与后缀式有一点不同：对于前缀式， //栈顶的符号优先级要大于即将要放入栈的符号的优先级， //然后输出栈顶符号‘*’或‘/’，然后再将当前符号放入栈内； //而对于后缀式，栈顶的符号优先级要大于等于当前符号的优先级，然后将栈顶符号‘*’或‘/’或‘+’或‘-’输出，然后再讲当前符号放入栈内。 memset(a,0,sizeof(a));   //清空a字符串数组      stack<char>sl;   //这是参数化模板，声明存放char类型的stack容器     cnt=0;  //初始化     for(int i=0; i<len; i++)  //分情况讨论1.2.3.4.5.6     {           if(n[i]<='z'&&n[i]>='a')               a[cnt++]=n[i];   //讲"常数"按次序存放在字符数组中         else if(n[i]=='(')               sl.push(n[i]);  //如果遇到右括号，进栈         else if(n[i]==')')  //如果遇到左括号，清栈         {               while(sl.top()!='('&&!sl.empty())               {  //直到遇到右括号或者栈空，停止出栈                 a[cnt++]=sl.top();  //将出栈的元素保存在字符数组中                 sl.pop();  //抛出栈顶元素             }               sl.pop();   //抛出'(';         }           else if(n[i]=='+'||n[i]=='-')           {               if(f) //前序排列  栈顶元素优先级高于当前逻辑运算符，让逻辑运算符进栈！              {                   while(!sl.empty()&&sl.top()!='('&&(sl.top()=='*'||sl.top()=='/'))                   {                       a[cnt++]=sl.top(); //将出栈的元素保存在字符数组中                      sl.pop(); //抛出栈顶元素                 }               }               else //后序排列  栈顶元素优先级高于要进栈元素，进栈                  while(!sl.empty()&&sl.top()!='(')  //不是空栈，不是'('                 {                       a[cnt++]=sl.top();  //将出栈的元素保存在字符数组中                      sl.pop();  //抛出栈顶元素                 }               sl.push(n[i]);   //进栈         }           else if(n[i]=='*'||n[i]=='/')           {               while(!sl.empty()&&sl.top()!='('&&(sl.top()=='*'||sl.top()=='/'))               {                   a[cnt++]=sl.top();   //将出栈的元素保存在字符数组中                 sl.pop();  //抛出栈顶元素             }               sl.push(n[i]);  //进栈         }       }       while(!sl.empty())   //清空栈，并保存元素     {           a[cnt++]=sl.top();           sl.pop();       }  } int main()   {       char st[150],sa[150];       memset(st,0,sizeof(st));         //清除原字符串       memset(a,0,sizeof(a));           //清除经转换后的字符串       memset(sa,0,sizeof(sa));         //清除倒置的字符串，用以转换前缀式       while(~scanf("%s",st))       {           len=strlen(st)-1;            //把字符“#”去掉           int i,j;           for(i=0,j=len-1; i<len; i++,j--)           {               if(st[j]=='(')                   sa[i]=')';               else if(st[j]==')')                   sa[i]='(';               else                   sa[i]=st[j];           }           solve(sa,1);                 //得到前缀式           for(i=cnt-1; i>=0; i--)               printf("%c",a[i]);           printf("\n");           for(i=0; i<len; i++)         //对于中缀式记得把括号去掉           {               if(st[i]!='('&&st[i]!=')')                   printf("%c",st[i]);           }           printf("\n");           solve(st,0);                 //得到后缀式           for(i=0; i<cnt; i++)               printf("%c",a[i]);           printf("\n");       }       return 0;   }  

转载于:https://www.cnblogs.com/CCCrunner/p/6444634.html

相关资源：算术表达式的求解（数据结构）