第三章
例如：Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 则它的
前缀式为： +*ab*-c/def
中缀式为： a*b+c-d/e*f
后缀式为： ab*cde/-fx+
综合比较它们之间的关系可得下列结论：
1.三式中的 “操作数之间的相对次序相同”;
(二叉树的三种访问次序中，叶子的相对访问次序是相同的)
2.三式中的 “运算符之间的的相对次序不同”;
3.中缀式丢失了括弧信息，致使运算的次序不确定;
(而前缀和后缀运算只需要一个存储操作数的栈，而中缀求值需要两个栈，符号栈和操
作数栈)
4.前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
5.后缀式的运算规则为：
·运算符在式中出现的顺序恰为表达式的运算顺序;
·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;
6.中缀求值的运算规则：
如果是操作数直接入栈。
如果是运算符。这与当前栈顶比较。个如果比当前栈顶高，则入栈，如果低则说明当前栈顶是最高的必须把他先运算完了。用编译原理的话就是说当前栈顶已经是最左素短语了)
其实中缀表达式直接求值和把中缀表达式转化成后缀表达式在求值的过程惊人的相似，只不过是直接求值是求出来，而转化成后缀是输出来。
中缀表达式直接求值算法：
OPNDType EvalueExpression()
{ //OPTR 和OPND分别为运算符栈和操作数栈
InitStack(OPTR);Push(OPTR,’#’);
InitStack(OPND);c=getchar();
While(c!=’#’|| GetTop(OPTR)!=’#’)
{
If(!IN(c,OP) ) //如果是操作数，直接入操作数栈
{ push(OPND,c);
c=getchar();
}
Else //如果是运算符，则与当前的栈顶比较
{
Switch(Precede(GetTop(OPTR),c))
{
Case ‘<’: push(OPTR,c);//比当前栈顶高，这入栈
c=getchar();
break;
Case ’= ’:Pop(OPTR,x); //在我们设计的优先级表中，
c=getchar(); //只有’(’和’)’存在相等的情况，
break; //而在规约中间只存在‘(’‘)’
//所以我们直接把’(’弹出就可以了
Case ‘>’: //比当前栈顶低，则要把栈顶先运算完(先规约)
pop(OPTR,theta); //把栈顶运算符弹出
Pop(OPND,b); //取出操作数，并且是前操作数
Pop(OPND,a); //在下面(栈的先进后出)
Push(OPND,Operate(a,theta,b)); //运算的结果入栈
//(他是其他运算符的操作数)
Break;
}//Switch
}//else
}//whild
Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。
}
中缀表达式转化成后缀表达式算法
void trans-post(char E[n] ,char B[n]) //中、后缀表达式转换//
{ //E[n]是中缀表达式、B[n]是后缀表达式存储的空间
int i=0,j=0; char x; stype S;
Clearstack(S); Push(S,‘#’);//‘#’入栈//
do {
x=E[i++] ; //扫描当前表达式分量//
if (x=‘#’) //到了中缀表达式最后了
while(!Emptystack(S)) //全部退栈,#和#是优先级最低的，
B[j++]==pop(S); //所以当前栈的所有运算都要规约
//输出栈顶运算符，并退栈直到遇见栈底的开始放进去的那个#//
else if (isdigit(x))
B[j++]=x; //操作数直接输出//
else if (x=‘)’) //遇到)那么就一定要找到(
{
while (Getstop(S)!=‘(’)
B[j++]=pop(S); //输出栈顶，并退栈//
pop(S); //退掉‘(’//
}
else //x为运算符//
{
while (precede(Getstop(S), x)) //栈顶( q1)与x比较//
B[j++]=pop(S); // q1 >=x时，输出栈顶符并退栈//
Push(S,x); // q1 < x时x进栈//
}
} while (x!=’#’);
B[j]=’#’;
} //置表达式结束符//
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：
https://www.87dh.com/xl/