首页 > 代码库 > 数据结构之 栈和队列---算术表达式的转换（前缀+中缀+后缀）
数据结构之 栈和队列---算术表达式的转换（前缀+中缀+后缀）
算术表达式的转换
Time Limit: 1000MS Memory limit: 65536K
题目描述
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。
输入
输入一算术表达式，以\‘#\‘字符作为结束标志。（数据保证无空格,只有一组输入）
输出
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。
示例输入
a*b+(c-d/e)*f#
示例输出
+*ab*-c/defa*b+c-d/e*fab*cde/-f*+
写完这个代码，想死的心都有了，修了半天的bug
代码：
#include <string>#include <iostream>#include<stdio.h>#include<string.h>#include <algorithm>#include <queue>#include <stack>using namespace std;int cmp(char ch) //给运算符定义一个数值表示优先级大小{ if(ch==‘+‘ || ch==‘-‘) return 1; else if(ch==‘*‘ || ch==‘/‘ ) return 2; else if(ch==‘)‘ || ch==‘(‘ ) return 3; //括号的优先级最高}void Pre(char s[], int len ){ int i, j; char a[200]; int e=0; for(i=len-2; i>=0; i--) { a[e++]=s[i]; } stack<char>ff; stack<char>gg; char dd; for(i=0; i<e; i++) { if(a[i]>=‘a‘ && a[i]<=‘z‘) { ff.push(a[i]); } else //如果是运算符的？ { if(a[i]==‘)‘) gg.push(a[i]); else if( a[i]==‘(‘ ) { while(gg.top()!=‘)‘ ) { dd=gg.top(); gg.pop(); ff.push(dd); } gg.pop(); } else // + - * / { if( !gg.empty() && (cmp(gg.top() )> cmp(a[i])) ) //栈顶元素优先级大 { if(gg.top()==‘)‘) { gg.push(a[i]); } else { dd=gg.top(); gg.pop(); ff.push(dd); gg.push(a[i]); } } else { gg.push(a[i]); } } } } while(!gg.empty()) { dd=gg.top(); ff.push(dd); gg.pop(); } while(!ff.empty()) { dd=ff.top(); cout<<dd; ff.pop(); } cout<<endl;}void In(char s[], int len){ int i; for(i=0; i<len-1; i++) { if(s[i]==‘(‘ || s[i]==‘)‘) continue; else cout<<s[i]; } cout<<endl;}void Post(char s[], int len){ stack<char>q; int i; for(i=0; i<len-1; i++) { if(s[i]>=‘a‘ && s[i]<=‘z‘) { cout<<s[i]; } else { if(q.empty()) { q.push(s[i]); } else //栈非空 { if(s[i]==‘(‘) { q.push(s[i]); } else if(s[i]==‘+‘) { if(q.top()==‘(‘ ) { q.push(s[i]); } else { cout<<q.top(); q.pop(); q.push(s[i]); } } else if(s[i]==‘-‘) { if(q.top()==‘(‘) { q.push(s[i]); } else { cout<<q.top(); q.pop(); q.push(s[i]); } } else if(s[i]==‘*‘) { if(q.top()==‘(‘ || q.top()==‘+‘ || q.top()==‘-‘ ) { q.push(s[i]); } else { cout<<q.top(); q.pop(); q.push(s[i]); } } else if(s[i]==‘/‘) { if(q.top()==‘+‘ || q.top()==‘-‘ || q.top()==‘(‘) { q.push(s[i]); } else { cout<<q.top(); q.pop(); q.push(s[i]); } } else if(s[i]==‘)‘) { while(q.top()!=‘(‘) { cout<<q.top(); q.pop(); } q.pop(); //将左括号弹出 } } } } while(!q.empty()) { cout<<q.top(); q.pop(); }}int main(){ char s[200]; int len; int i, j; scanf("%s", s); len=strlen(s); Pre(s, len); In(s, len); Post(s, len); cout<<endl; return 0;}
数据结构之 栈和队列---算术表达式的转换（前缀+中缀+后缀）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。