首页 算法🧠

表达式转换

中缀转前缀

假设有一个中缀表达式 1+((2+3)*4)-5

使用双栈法,首先构造操作数栈和运算符栈(这两个栈不能以字面意思理解,后期会混放,运算符栈属于临时的),然后从右至左扫描中缀表达式。

如果扫描是操作数则直接压入操作数栈;如果扫描是运算符, 是右括号直接放入,是左括号那就把运算符栈中右括号到栈顶的 元素弹出,压入操作数栈。如果是别的运算符就需要比较优先级: 若运算符优先级大于等于栈顶元素,则入栈,否则栈内元素出栈 压入操作数栈。

最后若运算符栈还有元素,那就再弹出压入操作数栈,之后将操作数栈翻转便是转化成为前缀表达式。

中缀转前缀图解

中缀表达式转化为前缀表达式

中缀转换后缀

假设有一中缀表达式 1 + (( 2 + 3)* 4 ) – 5

采用双栈法,构造一个操作数栈和运算符栈,从左往右遍历中缀表达式,当读到操作数时直接放入操作数栈。当读到运算符时,运算符栈顶元素为空,直接放入。如果运算符是“(”,直接压入栈中,如果运算符是“)”,那就将栈元素弹出压入操作数栈。否则比较优先级,若栈顶元素优先级低,直接入栈;否则就把栈顶元素弹出压入操作数栈,直到遇见栈顶元素优先级低的,然后该元素才能压入运算符栈。中缀表达式读取完后,将运算符栈中的元素压入操作数栈。

中缀转后缀图解

中缀表达式转化为前缀表达式

表达式求值

前缀与后缀计算区别

前缀表达式计算后缀表达式计算
扫描顺序从右到左从左到右
操作数栈操作数栈
遇到操作数时压栈压栈
遇到运算符时出栈出栈
出栈计算先弹出操作数 1 命名 为a,再弹出操作数 2 命名为b,a 在前计算先弹出操作数 1 命名 为a,再弹出操作数 2 命名为b,b 在前计算
结果运算符中唯一一个数运算符中唯一一个数

前缀表达式求值算法简单描述

前缀表达式只用了一个栈(我称为操作数栈),首先从右向左扫描。遇到操作数直接入栈;遇到运算符,按翻转的顺序(与后缀表达式相反的顺序)出栈计算,然后结果入栈。按照以上规则,扫描完成后,操作数栈中唯一一个数字即为结果。

前缀表达式求值图解

前缀表达式求值算法图解

中缀表达式求值算法简单描述

采用双栈法,首先构建两个栈,从左向右扫描,如果扫描到数字,直接放入操作数栈;如果扫描到运算符,运算符栈为空直接放入,否则比较优先级,栈顶优先级高,需要出栈计算:操作数按顺序出栈,运算符出栈,进行计算,将结果放入操作数栈, 之前的运算符入栈。按照以上规则一直扫描完,然后去看运算符栈中是否有运算符,有的话出栈操作,即可得到结果。

中缀表示式求值图解

中缀表达式求值算法图解

后缀表达式求值算法简单描述

首先设置一个操作数栈,从左往右扫描整个后缀表达式。如果是操作数,则将操作数压入栈中;如果是运算符,则从栈中弹出对应的操作数,根据操作数进行运算并将结果压入栈中;扫描完毕后,操作数栈中仅有一个元素,即为结果。

后缀表达式求值图解

后缀表达式求值算法图解




文章评论

目录