算法(4th ed)(122):基础——背包、队列和栈 5.1.7

阅读数:8 2019 年 11 月 6 日 07:29

算法(4th ed)(122):基础——背包、队列和栈 5.1.7

(API:算术表达式求值)

我们要学习的另一个栈用例同时也是展示泛型的应用的一个经典例子。我们在 1.1 节中最初学习的几个程序之一就是用来计算算术表达式的值的,例如:

复制代码
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

如果将 4 乘以 5,把 3 加上 2,取它们的积然后加 1,就得到了 101。但 Java 系统是如何完成这些运算的呢?不需要研究 Java 系统的构造细节,我们也可以编写一个 Java 程序来解决这个问题。它接受一个输入字符串(表达式)并输出表达式的值。为了简化问题,首先来看一下这份明确的递归定义:算术表达式可能是一个数,或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。简单起见,这里定义的是未省略括号的算术表达式,它明确地说明了所有运算符的操作数——你可能更熟悉形如 1 + 2 * 3 的表达式,省略了括号,而采用优先级规则。我们将要学习的简单机制也能处理优先级规则,但在这里我们不想把问题复杂化。为了突出重点,我们支持最常见的二元运算符 *+-/,以及只接受一个参数的平方根运算符 sqrt。我们也可以轻易支持更多数量和种类的运算符来计算多种大家熟悉的数学表达式,包括三角函数、指数和对数函数。我们的重点在于如何解析由括号、运算符和数字组成的字符串,并按照正确的顺序完成各种初级算术运算操作。如何才能够得到一个(由字符串表示的)算术表达式的值呢?E.W.Dijkstra 在 20 世纪 60 年代发明了一个非常简单的算法,用两个栈(一个用于保存运算符,一个用于保存操作数)完成了这个任务,其实现过程见下页,求值算法的轨迹如图 1.3.4 所示。

算法(4th ed)(122):基础——背包、队列和栈 5.1.7

图 1.3.4 Dijkstra 的双栈算术表达式求值算法的轨迹

表达式由括号、运算符和操作数(数字)组成。我们根据以下 4 种情况从左到右逐个将这些实体送入栈处理:

  • 操作数压入操作数栈;
  • 运算符压入运算符栈;
  • 忽略括号;
  • 在遇到括号时,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个右括号之后,操作数栈上只会有一个值,它就是表达式的值。这种方法乍一看有些难以理解,但要证明它能够计算得到正确的值很简单:每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时,它都将运算符和操作数的计算结果压入操作数栈。这样的结果就好像在输入中用这个值代替了该子表达式,因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。例如,用该算法计算以下表达式得到的结果都是相同的:

复制代码
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
( 1 + ( 5 * ( 4 * 5 ) ) )
( 1 + ( 5 * 20 ) )
( 1 + 100 )
101

本页中的 Evaluate 类是该算法的一个实现。这段代码是一个简单的“解释器”:一个能够解释给定字符串所表达的运算并计算得到结果的程序。

Dijkstra 的双栈算术表达式求值算法

复制代码
public class Evaluate
{
public static void main(String[] args)
{
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty())
{ // 读取字符,如果是运算符则压入栈
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")"))
{ // 如果字符为 ")",弹出运算符和操作数,计算结果并压入栈
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} // 如果字符既非运算符也不是括号,将它作为 double 值压入栈
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}

这段 Stack 的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型:将一个字符串解释为一段程序并执行该程序得到结果。有了泛型,我们只需实现 Stack 一次即可使用 String 值的栈和 Double 值的栈。简单起见,这段代码假设表达式没有省略任何括号,数字和字符均以空白字符相隔。

复制代码
% java Evaluate
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
101.0
% java Evaluate
( ( 1 + sqrt ( 5.0 ) ) / 2.0 )
1.618033988749895

评论

发布