前缀、中缀、后缀表达式

  • 时间:
  • 浏览:5

与前缀表达式这些,而且顺序是从左至右:

从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的有二个 数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

所谓中缀表达式,而且将函数名装到去去有二个 操作数上面的表达式,其中,左侧的操作数代表函数对象或值,右侧的操作数代表函数的参数值。这些:

这些前缀表达式“- × + 3 4 5 6”计算的步骤如下:

(1) 从右至左扫描,将6、5、4、3压入堆栈;

(2) 遇到+运算符,而且弹出3和4(3为栈顶元素,4为次顶元素,注意与后缀表达式做比较),计算出3+4的值,得7,再将7入栈;

(3) 接下来是×运算符,而且弹出7和5,计算出7×5=35,将35入栈;

(4) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

可不需要能 看出,用计算机计算前缀表达式的值是很容易的。

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的有二个 数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

遵循以下步骤:

(1) 初始化有二个 栈:运算符栈S1和储存上面结果的栈S2;

(2) 从右至左扫描中缀表达式;

(3) 遇到操作数时,将其压入S2;

(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:

(4-1) 肯能S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;

(4-2) 而且,若优先级比栈顶运算符的较高或相等,也将运算符压入S1;

(4-3) 而且,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;

(5) 遇到括号时:

(5-1) 肯能是右括号“)”,则直接压入S1;

(5-2) 肯能是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将你这些 对括号丢弃;

(6) 重复步骤(2)至(5),直到表达式的最左边;

(7) 将S1中剩余的运算符依次弹出并压入S2;

(8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。

在函数式编程语言中,为了表示方便,出現了你这些新的语法格式。所谓前缀、中缀、后缀表达式,它们之间的区别在于运算符相对与操作数的位置不同,为了说明它们的概念,首先来看一下中缀表达式。

前缀表达式又称为前缀记法、波兰式,主要用于表示运算符处在操作数以后 的表达式。

中缀表达式又称为中缀记法,操作符以中缀形式处在操作数的上面。

中缀表达式是亲戚亲戚大伙常用的算术表示土办法,觉得人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很比较复杂的,而且计算表达式的值时,通常要能 先将中缀表达式转换为前缀或后缀表达式,而且再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

与转换为前缀表达式这些,遵循以下步骤:

(1) 初始化有二个 栈:运算符栈S1和储存上面结果的栈S2;

(2) 从左至右扫描中缀表达式;

(3) 遇到操作数时,将其压入S2;

(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:

(4-1) 肯能S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

(4-2) 而且,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况表);

(4-3) 而且,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;

(5) 遇到括号时:

(5-1) 肯能是左括号“(”,则直接压入S1;

(5-2) 肯能是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将你这些 对括号丢弃;

(6) 重复步骤(2)至(5),直到表达式的最右边;

(7) 将S1中剩余的运算符依次弹出并压入S2;

(8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不需要逆序)。

这些后缀表达式“3 4 + 5 × 6 -”的计算步骤如下:

(1) 从左至右扫描,将3和4压入堆栈;

(2) 遇到+运算符,而且弹出4和3(4为栈顶元素,3为次顶元素,注意与前缀表达式做比较),计算出3+4的值,得7,再将7入栈;

(3) 将5入栈;

(4) 接下来是×运算符,而且弹出5和7,计算出7×5=35,将35入栈;

(5) 将6入栈;

(6) 最后是-运算符,计算出35-6的值,即29,由此得出最终结果。

后缀表达式又称为后缀记法、逆波兰式,后缀表达式与前缀表达式这些,而且运算符处在操作数以后 。