词条 | 后缀表达式 |
释义 | 后缀表达式不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 * 表达式的计算运用后缀表达式进行计算的具体做法: 建立一个栈S 。从左到右读后缀表达式,如果读到操作数就将它压入栈S中,如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算,再将运算的结果代替原栈顶的n项,压入栈S中 。如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。 表达式之间的转换计算机实现转换: 将中缀表达式转换为后缀表达式的算法思想: ·开始扫描; ·数字时,加入后缀表达式; ·运算符: a. 若为 '(',入栈; b. 若为 ')',则依次把栈中的的运算符加入后缀表达式中,直到出现'(',从栈中删除'(' ; c.剩下的运算符中, 若其优先级高于其它所有的运算符,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或者遇到了一个左括号就停止。 ·当扫描的中缀表达式结束时,栈中的的所有运算符出栈; 人工实现转换 这里我给出一个中缀表达式:a+b*c-(d+e) 第一步:按照运算符的优先级对所有的运算单位加括号:式子变成了:((a+(b*c))-(d+e)) 第二步:转换前缀与后缀表达式 前缀:把运算符号移动到对应的括号前面 则变成了:-( +(a *(bc)) +(de)) 把括号去掉:-+a*bc+de 前缀式子出现 后缀:把运算符号移动到对应的括号后面 则变成了:((a(bc)* )+ (de)+ )- 把括号去掉:abc*+de+- 后缀式子出现 发现没有,前缀式,后缀式是不需要用括号来进行优先级的确定的。如表达式:3+(2-5)*6/3 后缀表达式 栈 3_________________+ 3 ________________+( 3 2 _______________+(- 3 2 5 -_____________ + 3 2 5 - _____________+* 3 2 5 - 6 * ___________+/ 3 2 5 - 6 *3 __________+/ 3 2 5 - 6 *3 /+________ ("_____"用于隔开后缀表达式与栈) 另外一个人认为正确的转换方法: 遍历中缀表达式的每个节点,如果: 1、 该节点为操作数: 直接拷贝进入后缀表达式 2、 该节点是运算符,分以下几种情况: A、 为“(”运算符: 压入临时堆栈中 B、 为“)”运算符: 不断地弹出临时堆栈顶部运算符直到顶部的运算符是“(”为止。并把弹出的运算符都添加到后缀表达式中 C、 为其他运算符,有以下步骤进行: 比较该运算符与临时栈栈顶指针的运算符的优先级,如果临时栈栈顶指针的优先级高于该运算符的优先级,弹出并添加到后缀表达式中,反复执行前面的比较工作,直到遇到一个栈顶指针的优先级低于或等于该运算符的优先级,停止弹出添加并把该运算符压入栈中。 此时的比较过程如果出现栈顶的指针为‘(’,则停止循环并把该运算符压入栈中,注意:‘(’不要弹出来。 遍历完中缀表达式之后,检查临时栈,如果还有运算符,则全部弹出,并添加到后缀表达式中。 表达式之间的转换 c++代码#include <stack> #include <vector> #include <iostream> #include <algorithm> using namespace std; bool isOper(char c) //判断是否为操作符 { if ((c== '+ ')||(c== '- ')||(c== '* ')||(c== '/ ')||(c== '( ')||(c== ') ')) return true; return false; } bool isHigh(char top_op,char InfixExp_op) //判断操作符的优先级 //top_op为栈顶操作符 //InfixExp_op为当前读入操作符 //如果栈顶操作符优先级高,则弹出栈顶操作符 //如果栈顶操作符优先级低,则压入当前读入操作符 { if ((top_op== '+ ')&&(InfixExp_op== '+ ')) return true; if ((top_op== '+ ')&&(InfixExp_op== '- ')) return true; if ((top_op== '- ')&&(InfixExp_op== '+ ')) return true; if ((top_op== '- ')&&(InfixExp_op== '- ')) return true; if ((top_op== '* ')&&(InfixExp_op== '+ ')) return true; if ((top_op== '* ')&&(InfixExp_op== '- ')) return true; if ((top_op== '* ')&&(InfixExp_op== '* ')) return true; if ((top_op== '* ')&&(InfixExp_op== '/ ')) return true; if ((top_op== '/ ')&&(InfixExp_op== '+ ')) return true; if ((top_op== '/ ')&&(InfixExp_op== '- ')) return true; if ((top_op== '/ ')&&(InfixExp_op== '* ')) return true; if ((top_op== '/ ')&&(InfixExp_op== '/ ')) return true; if (InfixExp_op== ') ') return true; return false; } void input(vector <char> *InfixExp) { char c; cin> > c; while(c!= '$ ') { InfixExp-> push_back(c); cin> > c; } } void output(vector <char> *postfixExp) { vector <char> ::iterator postfixExp_it;//后缀表达式迭代器 for(postfixExp_it=postfixExp-> begin();postfixExp_it!=postfixExp-> end();postfixExp_it++) cout < <*postfixExp_it < < " "; cout < <endl; } void output2(vector <char> *postfixExp) //不输出括号 //如果表达式中括号不配对 //则可能有多余的括号未弹出 { vector <char> ::iterator postfixExp_it;//后缀表达式迭代器 for(postfixExp_it=postfixExp-> begin();postfixExp_it!=postfixExp-> end();postfixExp_it++) { if ((*postfixExp_it!= '( ')&&(*postfixExp_it!= ') ')) cout < <*postfixExp_it < < " "; } cout < <endl; } void main() { stack <char> mystack; vector <char> InfixExp;//中缀表达式 vector <char> ::iterator InfixExp_it;//中缀表达式迭代器 vector <char> postfixExp;//后缀表达式 do { cout < < "Please input a formula, ended by $: " < <endl; input(&InfixExp); //输入表达式 output(&InfixExp); for(InfixExp_it=InfixExp.begin();InfixExp_it!=InfixExp.end();InfixExp_it++) { if (!isOper(*InfixExp_it)) //操作数,直接输出 postfixExp.push_back(*InfixExp_it); else //操作符 { if (mystack.empty()) //栈为空,压入操作符 mystack.push(*InfixExp_it); else if(isHigh(mystack.top(),*InfixExp_it)) //栈顶操作符优先,比如栈顶为*,当前操作符为+,则弹出* { if (*InfixExp_it!= ') ') //非闭括号 //弹出栈中操作符直到栈顶操作数优先级低于当前读入操作数 //压入当前读入操作符 { do { postfixExp.push_back(mystack.top()); mystack.pop(); }while((!mystack.empty())&&(isHigh(mystack.top(),*InfixExp_it))); mystack.push(*InfixExp_it); } else //闭括号 { while((!mystack.empty())&&(mystack.top()!= '( ')) //弹出直到开括号 { postfixExp.push_back(mystack.top()); mystack.pop(); } if ((!mystack.empty())&&(mystack.top()== '( ')) mystack.pop(); //弹出开括号 } } else if(!isHigh(mystack.top(),*InfixExp_it)) //中缀表达式中操作符优先 //比如栈顶为+,而当前读入* { mystack.push(*InfixExp_it); //压入当前读入操作符 } } } while(!mystack.empty()) //把栈中剩余的操作符依次弹出 { postfixExp.push_back(mystack.top()); mystack.pop(); } output2(&postfixExp); while(!mystack.empty()) mystack.pop(); InfixExp.clear(); postfixExp.clear(); //清空栈、中缀表达式和后缀表达式 }while(true); } 中缀表达式转成后缀表达式 pascalprogram p2_29; const max=100; op_set:set of char=['+','-','*','/']; letter:set of char=['0'..'9']; var expression,result:string; procedure sean(expression:string); var i,top1,top2:integer; ovs:array [1..max] of string[max]; ops:array [1..max] of char; f:array ['#'..'/','#'..'/'] of shortint; begin f['+','+']:=1; f['+','-']:=1; f['+','*']:=-1; f['+','/']:=-1; f['+','(']:=-1; f['+',')']:=1; f['+','#']:=1; f['-','+']:=1; f['-','-']:=1; f['-','*']:=-1; f['-','/']:=-1; f['-','(']:=-1; f['-','}']:=1; f['-','#']:=1; f['*','+']:=1; f['*','-']:=1; f['*','*']:=1; f['*','/']:=1; f['*','(']:=-1; f['*',')']:=1; f['*','#']:=1; f['/','+']:=1; f['/','-']:=1; f['/','*']:=1; f['/','/']:=1; f['/','(']:=-1; f['/',')']:=1; f['/','#']:=1; f['(','+']:=-1; f['(','-']:=-1; f['(','*']:=-1; f['(','/']:=-1; f['(','(']:=-1; f['(',')']:=0; f['(','#']:=2; f[')','+']:=2; f[')','-']:=2; f[')','*']:=2; f[')','/']:=2; f[')','(']:=2; f[')',')']:=2; f[')','#']:=2; f['#','+']:=-1; f['#','-']:=-1; f['#','*']:=-1; f['#','/']:=-1; f['#','(']:=-1; f['#',')']:=2; f['#','#']:=0; {优先级设置} expression:=expression+'#';{末尾加标志} ops[1]:='#'; top1:=0; top2:=1; for i:=1 to length(expression) do {逐个扫描} begin if expression[i] in letter then {是数字就进栈} begin inc(top1); ovs[top1]:=expression[i]; end else begin {运算符} while f[ops[top2],expression[i]]=1 do {栈顶运算符优先级高于当前运算符} begin {取栈顶上面的两个元素运算后,再压栈} ovs[top1-1]:=ovs[top1-1]+ovs[top1]+ops[top2]; top1:=top1-1; dec(top2); end; if f[ops[top2],expression[i]]=0 then top2:=top2-1 {优先级相同,则抵消} else {栈顶运算符优先级低于当前运算符,则压栈} begin top2:=top2+1; ops[top2]:=expression[i]; end; end; end; result:=ovs[1];{返回结果} end; begin readln(expression); sean(expression); writeln(result); readln; end. 后缀表达式的求值 pascal注:输入时符号和数字要空一格 program p2_30a; const maxn=20; var stack:array [1..maxn] of integer; s:string; function comp(s:string):integer; var ch:char; i,top,x,y,z:integer; begin top:=0; i:=1; ch:=s[i]; while i<=length(s) do {逐个位数判断} begin case ch of '0'..'9':begin x:=0; while (ch<>' ') do begin x:=x*10+ord(ch)-ord('0'); {当前数位} i:=i+1; ch:=s[i];{下一位} end; inc(top); stack[top]:=x; end; '+':begin x:=stack[top]; dec(top); y:=stack[top];{获得两个数} z:=y+x; {计算} stack[top]:=z; {存值} end; '-':begin x:=stack[top]; dec(top); y:=stack[top];{获得两个数} z:=y-x; {计算} stack[top]:=z; {存值} end; '*':begin x:=stack[top]; dec(top); y:=stack[top];{获得两个数} z:=y*x; {计算} stack[top]:=z; {存值} end; '/':begin x:=stack[top]; dec(top); y:=stack[top];{获得两个数} z:=y div x; {计算} stack[top]:=z; {存值} end; end; inc(i); ch:=s[i]; end; exit(stack[top]); end; begin readln(s); writeln(comp(s)); readln; end. |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。