计算机考研:数据结构常用算法分析(三)？

例如: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.后缀类型的运算规则是:

& ampmiddot运算符在公式中出现的顺序正好是表达式的运算顺序；

& ampmiddot的每个运算符和出现在它之前和附近的两个操作数构成一个最小表达式；

6.中缀求值的算术规则:

如果是操作数，则直接放入堆栈。

如果是运营商。这是与当前堆栈顶部进行比较。如果它高于当前栈顶，则将其放入栈中。如果低，说明当前栈顶最高，必须先计算。根据编译原理，当前栈顶已经是最左边的素数短语)

其实中缀表达式的直接求值和中缀表达式转换成后缀表达式的过程惊人的相似，只不过直接求值是为了找出，而转换成后缀是为了输出。

中缀表达式的直接求值算法:

OPNDType EvalueExpression()

{//OPTR和OPND分别是操作符栈和操作数栈。

init stack(OPTR)；Push(OPTR，' # ')；

init stack(OPND)；c = getchar()；

而(c！='#'|| GetTop(OPTR)！='#')

{

如果(！IN(c，OP)) //如果是操作数，直接进入操作数栈。

{ push(OPND，c)；

c = getchar()；

}

Else //如果是运算符，则与当前栈顶进行比较。

{

switch(precend(GetTop(OPTR)，c))

{

大小写' & lt':push(OPTR，c)；//高于放入堆栈的当前栈顶。

c = getchar()；

打破；

Case '= ':Pop(OPTR，x)；//在我们设计的优先级表中，

c = getchar()；//只有“(”和“)”相等。

打破；//而规范中间只有'(' ')'。

//所以我们可以只弹出'('。

大小写“>”://如果低于当前栈顶，应该先计算栈顶(先指定)。

pop(OPTR，theta)；//弹出栈顶运算符。

Pop(OPND，b)；//取操作数，是前一个操作数。

Pop(OPND，a)；//在底部(堆栈中先入后出)

Push(OPND，Operate(a，theta，b))；//操作的结果放入堆栈。

//(他是其他运算符的操作数)

打破；

}//开关

}//否则

}//whild

返回GetTop(OPND)；//最后留在操作数堆栈里的是整个表达式的结果。

}

如果你对考研有疑问，不知道考研中心的内容怎么总结，不了解考研报名的地方政策，点击最下方咨询官网，免费获取复习资料:/xl/