首页 > 代码库 > sicily 中缀表达式转后缀表达式
sicily 中缀表达式转后缀表达式
题目描述
将中缀表达式（infix expression）转换为后缀表达式（postfix expression）。假设中缀表达式中的操作数均以单个英文字母表示，且其中只包含左括号‘(‘，右括号‘)’和双目算术操作符+，-，*，/。
输入格式
第一行是测试样例个数n。
以下n行，每行是表示中缀表达式的一个字符串（其中只包含操作数和操作符和左右括号，不包含任何其他字符），长度不超过100个字符。
输出格式
为每一个测试样例单独一行输出对应后缀表达式字符串（其中只包含操作数和操作符，不包含任何其他字符）
样例输入
将样例输入复制到剪贴板2 A+B*C-D-E/Fa+(b-c)*d+e/f
样例输出
ABC*+D-EF/-abc-d*+ef/+
解法一：(已AC)
#include <iostream>#include <string>#include <stack> using namespace std;bool isoper(char a){ if(a==‘+‘||a==‘-‘||a==‘*‘||a==‘/‘||a==‘%‘) return true; else return false;}int rank(char a){ if(a==‘*‘||a==‘/‘||a==‘%‘) return 3; else return 1;}int main(){ stack<char> op; string str; cin>>str; int i,len= str.length(); for(i=0;i<len;i++) { if(!isoper(str[i])) cout<<str[i]; else { if(op.empty()) op.push(str[i]); else { while(!op.empty()&&rank(op.top())>=rank(str[i])) { cout<<op.top(); op.pop(); } op.push(str[i]); } } } while(!op.empty()) { cout<<op.top(); op.pop(); } return 0;}
解法二：(目前提提示答案错误，这里先搁置一段，回看)
#include <iostream>#include <stack>#include <queue>#include <vector>#include <list>using namespace std;int main(){ string data; cin>>data; vector<char> temp; string out="";//等会再处理 list<char> fuhao; int count=0;//操作数，为2时就进栈 for(int i=0;i<data.length();++i){ if(data[i]==‘+‘||data[i]==‘-‘||data[i]==‘*‘||data[i]==‘/‘||data[i]==‘%‘){ fuhao.push_back(data[i]); } else if(count<2){ temp.push_back(data[i]); ++count; } else if(count==2){ if((fuhao.back()==‘*‘||fuhao.back()==‘/‘||fuhao.back()==‘%‘)&&(fuhao.front()==‘+‘||fuhao.front()==‘-‘)){ temp.push_back(data[i]); ++count; temp.push_back(fuhao.back()); --count; fuhao.pop_back(); } else if(fuhao.front()==‘*‘||fuhao.front()==‘/‘||fuhao.front()==‘%‘){ temp.push_back(fuhao.front()); --count; fuhao.pop_front(); ++count; temp.push_back(data[i]); } else if((fuhao.back()==‘+‘||fuhao.back()==‘-‘)&&(fuhao.front()==‘+‘||fuhao.front()==‘-‘)){ temp.push_back(fuhao.front()); --count; fuhao.pop_front(); ++count; temp.push_back(data[i]); } } } while(!fuhao.empty()){ temp.push_back(fuhao.back()); fuhao.pop_back(); } for(int i=0;i<temp.size();++i){ cout<<temp[i]; }}
本题虽然很简单，但是在第一次做的时候，忽略了%的情况。多做sicily上的题，看来确实可以锻炼思维，增加严谨性。
此题还有加括号一种，这里暂时搁置。还有另外两种方法。
sicily 中缀表达式转后缀表达式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。