JavaScript数据结构中栈的应用之表达式求值问题详解
背景
在JavaScript中,算术表达式很常见,例如 (2 + 3) * 4 - 8 / 2
。对于一个算术表达式,我们需要将它转化为一个数值。要对表达式求值,我们需要确定运算符优先级和结合性。其中,左结合表示从左到右计算,右结合表示从右到左计算。
步骤
我们可以用栈来求一个表达式的值。具体的求值过程如下:
-
遍历表达式中的每个字符。
-
对于数字字符,将它压入操作数栈。
-
对于运算符,将它压入操作符栈。在此之前,先对栈顶元素进行预处理:
a. 如果栈为空,或者栈顶元素是左括号(
,那么将它压入操作符栈。
b. 如果栈顶元素之间的运算符优先级小于等于当前操作符,那么将当前操作符压入操作符栈。
c. 如果栈顶元素之间的运算符优先级大于当前操作符,那么将栈顶运算符弹出,将操作数根据运算符进行计算,并将计算结果压入操作数栈,然后回到步骤3。
-
对于左括号`(,将其压入操作符栈。
-
对于右括号
),将操作符栈中的运算符不断弹出,直到遇到左括号
(,对这一部分表达式进行计算,将计算结果压入操作数栈。 -
如果表达式中的所有字符都遍历完毕,那么就将操作符栈中的元素依次弹出,并对表达式进行计算,将计算结果压入操作数栈。当操作符栈为空时,算术表达式的值等于操作数栈顶元素的值。
示例
下面我们来看一些例子:
示例1:基本表达式求值
考虑基本表达式 $x = (+ 2 3)
, 按照前面所述步骤求值:
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} "+" \ 2 \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} 2 \ 3 \ + \end{matrix}$
那么,算术表达式的值等于操作数栈顶元素的值,即 5。
示例2:复合表达式求值
再来看一个更复杂的表达式 (3 + 4 * 2 / (1 - 5) ^ 2 ^ 3)
,按照前面所述步骤求值:
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \ - \ 1 \end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \ - \ 1 \ ^ \ 2\end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \ - \ ( \ 1 \ - \ 5\end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \ - \ ( \ 1 \ - \ 5 \ ) \ ^ \ 2\end{matrix}$
$x =
$\begin{matrix} Stack \ Top \end{matrix}$ $\begin{matrix} + \ ( \ 3 \ / \ 2 \ * \ - \ ( \ 1 \ - \ 5 \ ) \ ^ \ 2 \ ^ \ 3\end{matrix}$
对于这个表达式,算出结果为-3.6597222222222223。
结论
我们可以用栈来求解算术表达式,同时可以在每个字符扫描到时进行不同的操作。在扫描过程中,使用两个栈。一个栈用来保存操作符,另一个栈用来保存操作数。根据运算符的优先级和结合性,我们可以将表达式转换为逆波兰表达式,然后进行计算。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:JavaScript数据结构中栈的应用之表达式求值问题详解 - Python技术站