学习了栈结构,你以为学完了栈?今天要讲的是中缀表达式转后缀表达式,后缀表达式的计算和中缀表达式的计算,接下来让我们开始吧!
什么是中缀表达式和后缀表达式?
中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)。与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被电脑解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。
与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来,用于指示运算的次序。
后缀表示法 (逆波兰表示法)(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 5”与“(3 - 4)5”不相同,但后缀记法中前者写做“3 4 5 -”,无歧义地表示“3 (4 5 ) -”;后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,并且能很快求值。
首先我们要进行的就是中缀表达式和后缀表达式的转换。开始吧!
中缀表达式转后缀表达式
首先让我们来了解一下有关中缀转后缀的算法,大概有以下几个规则:
(1)当读到数字直接送至输出队列中;
(2)当读到运算符t时:
a.将栈中所有优先级高于或等于t的运算符弹出,送到输出队列中;
b.t进栈;
(3)读到左括号时总是将它压入栈中;
(4)读到右括号时,将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至输出队列后,再丢弃左括号;
(5)中缀表达式全部读完后,若栈中仍有运算符,将其送到输出队列中。
符号的优先级
首先我们必须知道有关运算符优先级的问题,经过查阅,我们可以得到如下二维数组。
|
|
先找横行,代表栈中的运算符,再找纵行,代表你想要比较的运算符,-1
代表栈中符号优先级小于栈外符号优先级,栈外符号入栈;1
代表栈中符号优先级大于栈外符号优先级,栈中符号弹出,直到栈中符号优先级比栈外符号小,栈外符号入栈;0
代表优先级一样,暂时不进行考虑。
符号的比较函数
弄清楚符号的优先级,我们就可以对两个符号进行比较,具体实现代码如下:
|
|
将符号关系转换为数字更有利于我们之后的判断,接下来就是我们的正题来了。
构造一个栈
跟上一篇一样,我们需要构造一个基本的数据结构—-栈,来实现这个项目,不同的是,我们新增加了一个函数peek()
来获取栈顶的第一个元素。下面是代码实现:
|
|
构造好一个栈之后,我们就需要进行最重要的步骤了,构造转换函数。
中缀表达式转换函数
中缀表达式转后缀表达式跟C语言不同,JavaScript是一种弱类型语言,它的实现更加的灵活,首先我们在栈中先压入#
,令最后一个元素能够弹出,然后我们构造如下函数:
|
|
然后我们就可以输入中缀表达式进行计算了,注意在控制台计算的时候在中缀表达式的后面加一个#号,防止栈内符号未完全弹出的情况出现。
测试实例:Change('1+2*(3-1+2)-3#');
示例输出:1231-2+*+3-
注意,输出的是一个队,也就是一个数组,本样例是为了方便这样测试的。
后缀表达式的计算
相对于中缀表达式转后缀表达式,后缀表达式的计算就简单多了,直接上代码,在注释中进行讲解。
|
|
测试实例:suffix('1231-2+*+3-')
示例输出:6
注意后缀表达式的计算无需将符号入栈,只需要弹出数字进行运算即可。
中缀表达式的计算
中缀表达式的计算原理如果你理解了中缀转后缀、后缀运算那么很快你就能够理解,这个例子也是直接在代码中进行讲解。
|
|
本代码可以自行尝试输出和输入,根据这个原理以及少许html和CSS的基础就能够写出相当不错的计算器
计算器的实现:神奇的计算器
今天的代码就到这里,谢谢大家!