JavaScript数据结构中栈的应用之表达式求值问题详解

JavaScript数据结构中栈的应用之表达式求值问题详解

背景

在JavaScript中，算术表达式很常见，例如 (2 + 3) * 4 - 8 / 2。对于一个算术表达式，我们需要将它转化为一个数值。要对表达式求值，我们需要确定运算符优先级和结合性。其中，左结合表示从左到右计算，右结合表示从右到左计算。

步骤

我们可以用栈来求一个表达式的值。具体的求值过程如下：

1. 遍历表达式中的每个字符。

2. 对于数字字符，将它压入操作数栈。

3. 对于运算符，将它压入操作符栈。在此之前，先对栈顶元素进行预处理：

a. 如果栈为空，或者栈顶元素是左括号(，那么将它压入操作符栈。

b. 如果栈顶元素之间的运算符优先级小于等于当前操作符，那么将当前操作符压入操作符栈。

c. 如果栈顶元素之间的运算符优先级大于当前操作符，那么将栈顶运算符弹出，将操作数根据运算符进行计算，并将计算结果压入操作数栈，然后回到步骤3。

1. 对于左括号`(，将其压入操作符栈。

2. 对于右括号)，将操作符栈中的运算符不断弹出，直到遇到左括号(，对这一部分表达式进行计算，将计算结果压入操作数栈。

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。

结论

我们可以用栈来求解算术表达式，同时可以在每个字符扫描到时进行不同的操作。在扫描过程中，使用两个栈。一个栈用来保存操作符，另一个栈用来保存操作数。根据运算符的优先级和结合性，我们可以将表达式转换为逆波兰表达式，然后进行计算。