【数据结构】前缀、中缀、后缀表达式

一、概念1. 前缀表达式前缀表达式也称波兰式指运算符处于两个操作数的前面比如 2 3那么前缀表达式就是 2 3对于复杂点的表达式如 13 * ((3 8) * 4)前缀表达式为 * 13 * 3 8 4 。2. 中缀表达式中缀表达式是我们常用的算术表达式比如 2 9 - (32 * (19 - 4) 14) 人类很容易得出结果但计算机得进行优先级比较所以计算机更偏向于前缀、后缀表达式。3. 后缀表达式也称逆波兰式指运算符处于两操作数后面比如 2 3后缀表达式为 2 3 对于复杂点的表达式如 13 * ((3 8) * 4)后缀表达式为 13 3 8 4 * * 。二、计算方式注意本篇文章仅考虑正整数的情况负数请自行添加。1. 前缀计算前缀表达式* 13 * 3 8 4从右往左读读到数字就入栈读到符号就弹出两个数字进行运算并将结果压入栈。注意减法、除法运算为先弹出的数做减数、除数当表达式全部读完时栈中的唯一一个元素就是答案。● 计算过程从最右边开始向左读○ 读到数字4压入栈当前栈元素4○ 读到数字8压入栈当前栈元素4 8○ 读到数字3压入栈当前栈元素4 8 3○ 读到符号弹出两个元素3 8压入元素38 11当前栈元素4 11○ 读到符号*弹出两个元素4 11压入元素4*11 44当前栈元素44○ 读到数字13压入栈当前栈元素44 13○ 读到符号*弹出两个元素44 13压入元素44*13 572○ 表达式读取完毕弹出栈中的唯一一个元素 572 并输出● 参考代码#includeiostream//前缀表达式计算 #includestring//getline头文件 #includestack//栈的头文件 using namespace std; int getPrefixAnswer(string pns){//计算前缀表达式的值 stackintans; for(int ipns.size()-1;i0;i--){//从右往左读 //数字 int num0,sizeofNum1;//在num的左侧加上一位时需要用该数字乘以10的(num的位数)次方 bool ffalse;//用来判断是否为数字 while((0pns[i]9pns[i])(i0)){ ftrue; num(pns[i]-0)*sizeofNum; sizeofNum*10; i--; } if(f)ans.push(num);//入栈 else{//符号 int xans.top(); ans.pop(); int yans.top(),sum0; ans.pop(); switch(pns[i]){//枚举符号的种类 case :{//加号 sumyx; break; } case -:{//减号 sumy-x; break; } case *:{//乘号 sumy*x; break; } case /:{//除号 sumy/x; break; } default:break;//其他情况 } ans.push(sum);//结果入栈 } } } int main(){ string s; getline(cin,s);//中间有间隔整行读入 printf(%d\n,getPrefixAnswer(s));//printf()比cout更快 return 0; }2. 中缀计算这个......没什么好说的吧......● 计算过程如果是左括号直接进符号栈如果是操作运算符与符号栈的栈顶元素比较优先级如果高就压入栈低就取出符号栈顶的元素和数栈中的栈顶两个数进行运算然后把结果压回到数栈中接着再判断符号栈顶的元素和当前输入的符号继续比较优先级重复前面步骤直到栈空或者输入的符号优先级高如果是右括号把符号栈栈顶的元素取出如果不是左括号就取出数栈栈顶的两个数进行相应的运算把结果压回到数栈中直到符号栈中取出的符号是左括号当输入完表达式时判断符号栈是否为空不为空把符号栈栈顶的元素和数栈栈顶的两个数取出进行相应的运算把结果压回到数栈中直到符号栈为空。那最终的结果会存在数栈的栈顶。● 参考代码#includeiostream//中缀表达式求值 #includestring #includestack using namespace std; stackcharsymbol;//符号栈 stackintnumber;//数栈 void Evaluation(char sym){ if(number.size()2||symbol.size()1)return;//大坑防止程序出现意外查不出错此行代码保证不会RE或CE symbol.pop(); int xnumber.top(); number.pop(); int ynumber.top(); number.pop(); switch(sym){ case :xxy;break; case -:xy-x;break;//注意顺序 case *:xx*y;break; case /:xy/x;break; default:break; } number.push(x); } int getInsuffixAnswer(string s){ for(int i0;is.size();i){ //数字 int num-1; while(s[i]0s[i]9)nummax(num,0)*10(s[i]-0); if(num-1)number.push(num); switch(s[i]){ case (:symbol.push(();break; case :{//加减等级低靠边站 while(symbol.size()(symbol.top()*||symbol.top()/))Evaluation(symbol.top()); symbol.push(); break; } case -:{ while(symbol.size()(symbol.top()*||symbol.top()/))Evaluation(symbol.top()); symbol.push(-); break; } case /:{ while(symbol.size()symbol.top()*)Evaluation(symbol.top()); symbol.push(/); break; } case *:symbol.push(*);break;//乘等级最高不用考虑等级问题 case ):{//遇到右括号踢掉括起来的所有数字 while(symbol.top()!()Evaluation(symbol.top()); symbol.pop(); break; } default:break; } } while(!symbol.empty())Evaluation(symbol.top());//计算剩余项 return number.top();//此时数栈顶就是答案 } int main(){ string s; getline(cin,s); printf(%d\n,getInsuffixAnswer(s)); return 0; }3. 后缀计算后缀表达式13 3 8 4 * *从左向右读遇到数字就压栈遇到符号就弹出两个数字运算结果压回栈中。● 计算过程○ 读到数字13压入栈。当前栈元素13○ 读到数字3压入栈。当前栈元素13 3○ 读到数字8压入栈。当前栈元素13 3 8○ 读到符号弹出两个元素3 8压入结果 3 8 11 。当前栈元素13 11○ 读到数字4压入栈。当前栈元素13 11 4读到符号*弹出两个元素11 4压入结果 11 * 4 44 。当前栈元素13 44读到符号*弹出两个元素13 44压入结果 13 * 44 572 。当前栈元素572读取结束当前栈顶元素 572 即为答案。● 参考代码#includeiostream//后缀表达式求值 #includestring #includestack using namespace std; stackintnumber;//数字栈 int getSuffixAnswer(string s){ for(int i0;is.size();i){ if(s[i]0s[i]9){ int num0; while(s[i]0s[i]9)numnum*10(s[i]-0); number.push(num);//压栈 }else if(s[i]! ){ int xnumber.top(); number.pop(); int ynumber.top(); number.pop(); switch(s[i]){ case :xy;break; case -:xy-x;break; case *:x*y;break; case /:xy/x;break; default:break; } number.push(x); } } return number.top(); } int main(){ string s; getline(cin,s); printf(%d\n,getSuffixAnswer(s)); return 0; }三、转换方式1. 前缀表达式转中缀表达式可根据定义直接转换此处不再解释直接给出代码。#includeiostream//前缀表达式转中缀表达式 #includestring #includestack using namespace std; stackstringexpression;//表达式栈 string prefixToInfix(string s){ for(int is.size()-1;i0;i--){//从右向左扫描 if(s[i]0s[i]9){ string num; while(i0 s[i]0s[i]9)nums[i--]num; expression.push(num);//数字直接压栈 i;//补偿i-- }else if(s[i]! ){ string xexpression.top(); expression.pop(); string yexpression.top(); expression.pop(); string temp(xs[i]y);//组合成中缀表达式 expression.push(temp); } } return expression.top(); } int main(){ string s; getline(cin,s); coutprefixToInfix(s)endl; return 0; }2. 前缀表达式转后缀表达式#includestring #includestack #includevector using namespace std; bool isOperator(char c){ return c||c-||c*||c/; } int getPriority(char op){ if(op*||op/)return 2; if(op||op-)return 1; return 0; } string prefixToSuffix(string prefix){ stackstring st; reverse(prefix.begin(),prefix.end()); for(int i0;iprefix.size();i){ if(prefix[i] )continue; if(isdigit(prefix[i])){ string num; while(iprefix.size()isdigit(prefix[i]))numprefix[i]; i--; st.push(num); } else if(isOperator(prefix[i])){ string op1st.top(); st.pop(); string op2st.top(); st.pop(); string tempop1 op2 prefix[i]; st.push(temp); } } return st.top(); } int main(){ string prefix; getline(cin,prefix); coutprefixToSuffix(prefix)endl; return 0; }3. 中缀表达式转前缀表达式#includeiostream//中缀表达式转前缀表达式 #includestring #includestack #includealgorithm using namespace std; bool isOperator(char c){ return c||c-||c*||c/; } int getPriority(char op){ if(op*||op/)return 2; if(op||op-)return 1; return 0; } string infixToPrefix(string s){ stackcharoperators; stackstringoperands; reverse(s.begin(),s.end()); for(int i0;is.size();i){ if(s[i] )continue; if(s[i]))operators.push(s[i]); else if(s[i](){ while(!operators.empty()operators.top()!)){ string op1operands.top();operands.pop(); string op2operands.top();operands.pop(); char opoperators.top();operators.pop(); string temp; tempop; tempop2; tempop1; operands.push(temp); } operators.pop(); } else if(isOperator(s[i])){ while(!operators.empty()getPriority(operators.top())getPriority(s[i])){ string op1operands.top();operands.pop(); string op2operands.top();operands.pop(); char opoperators.top();operators.pop(); string temp; tempop; tempop2; tempop1; operands.push(temp); } operators.push(s[i]); } else{ string operand; while(is.size()(isdigit(s[i])||isalpha(s[i]))){ operands[i]; i; } i--; reverse(operand.begin(),operand.end()); operands.push(operand); } } while(!operators.empty()){ string op1operands.top();operands.pop(); string op2operands.top();operands.pop(); char opoperators.top();operators.pop(); string temp; tempop; tempop2; tempop1; operands.push(temp); } return operands.top(); } int main(){ string s; getline(cin,s); coutinfixToPrefix(s)endl; return 0; }4. 中缀表达式转后缀表达式#includeiostream//中缀表达式转后缀表达式 #includestring #includestack #includemap using namespace std; stackcharop;//运算符栈 mapchar,intpri{{,1},{-,1},{*,2},{/,2}};//优先级映射 string infixToSuffix(string s){ string res; for(int i0;is.size();i){ if(s[i]0s[i]9){ while(is.size()s[i]0s[i]9)ress[i]; res ; i--; } else if(s[i]() op.push(s[i]); else if(s[i])){ while(op.top()!(){ resop.top(); res ; op.pop(); } op.pop(); } else if(pri.count(s[i])){ while(!op.empty()op.top()!(pri[op.top()]pri[s[i]]){ resop.top(); res ; op.pop(); } op.push(s[i]); } } while(!op.empty()){ resop.top(); res ; op.pop(); } return res; } int main(){ string s; getline(cin,s); coutinfixToSuffix(s)endl; return 0; }5. 后缀表达式转前缀表达式#includeiostream #includestack #includealgorithm using namespace std; bool isOperator(char c){ return (c||c-||c*||c/); } string postfixToPrefix(string post_exp){ stackstrings; int lengthpost_exp.size(); for(int i0;ilength;i){ if(isOperator(post_exp[i])){ string op1s.top(); s.pop(); string op2s.top(); s.pop(); string temppost_exp[i]op2op1; s.push(temp); }else s.push(string(1,post_exp[i])); } string ans; while(!s.empty()){ anss.top(); s.pop(); } return ans; } int main(){ string post_exp; cinpost_exp; coutpostfixToPrefix(post_exp)endl; return 0; }6. 后缀表达式转中缀表达式#includeiostream #includestack #includestring #includevector using namespace std; bool isOperator(char c) { return c||c-||c*||c/; } string postfixToInfix(string postfix) { stackstringst; for(char c:postfix){ if(isOperator(c)){ string op2st.top(); st.pop(); string op1st.top(); st.pop(); string temp(op1 string(1,c) op2); st.push(temp); }else st.push(string(1,c)); } return st.top(); } int main(){ string postfix; cinpostfix; coutpostfixToInfix(postfix)endl; return 0; }本章内容就到这里感谢观看欢迎提出文章中的问题参考文献[原来的1024]前缀、中缀和后缀表达式详解中缀表达式到后缀表达式的转换规则以及后缀表达式的计算规则附计算代码[ByteFlys]【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式[ChanJose]C 中缀表达式的计算[奋斗的龙猫]中缀表达式转前缀、后缀表达式支持多位数字、小数的运算