算术表达式求值算法
咱们要学习的一个栈的用例同时也是展现泛型的应用的一个经典例子，就是用来计算算术表达式的值，例如数组
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )函数
若是将4乘以5，把3加上2，取它们的积而后加上1，就获得了101。但Java系统是如何完成这些运算的呢？不须要研究Java系统的构造细节，咱们也能够编写一个Java程序来解决这个问题。它接受一个输入字符串（表达式）并输出表达式的值。为了简化问题，首先来看一下这份明确的递归定义：算术表达式多是一个数，或者是由一个左括号、一个算术表达式、一个运算符、另外一个算术表达式和一个右括号组成的表达式。简单起见，这里定义的是未省略括号的算术表达式，它明确地说明了全部运算符的操做数——你可能更熟悉形如 1 + 2 * 3 的表达式，省略了括号，而采用优先级规则。咱们将要学习的简单机制也能处理优先级规则，但在这里咱们不想把问题复杂化。为了突出重点，咱们支持最多见的二元运算符*、+、-和/，以及只接受一个参数的平方根运算符sqrt。咱们也能够轻易支持更多数量和种类的运算符来计算多种你们熟悉的数学表达式，包括三角函数、指数和对数函数。咱们的重点在于如何解释由括号、运算符和数字组成的字符串，并按照正确的顺序完成各类初级算术运算操做。如何才可以获得一个（由字符串表示的）算术表达式的值呢？E.W.Dijkstra在20世纪60年代发明了一个很是简单的算法，用两个栈（一个用于保存运算符，一个用于保存操做数）完成了这个任务，其实现过程以下，运行轨迹如输出结果。学习
表达式由括号、运算符和操做数（数字）组成。咱们根据如下4种状况从左到右逐个将这些实体送入栈处理：lua
在处理完最后一个右括号以后，操做数栈上只会有一个值，它就是表达式的值。这种方法乍一看有些难以理解，但要证实它可以计算获得正确的值很简单：每当算法遇到一个被括号包围并由一个运算符和两个操做数组成的子表达式时，它都将运算符和操做数的计算结果压入操做数栈。这样的结果就像在输入中用这个值代替了该子表达式，所以用这个值代替子表达式获得的结果和原表达式相同。咱们能够反复应用这个规律并获得一个最终值。例如，用该算法计算如下表达式获得的结果都是相同的spa
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )code
( 1 + ( ( 5 ) * ( 4 * 5 ) ) )blog
( 1 + ( 5 * 20 ) )递归
( 1 + 100 )字符串
101
程序：
1 package com.beyond.algs4.experiment; 2 3 import com.beyond.algs4.lib.Stack; 4 import com.beyond.algs4.std.StdIn; 5 import com.beyond.algs4.std.StdOut; 6 7 public class Evaluate { 8 9 public static void main(String[] args) { 10 Stack<String> ops = new Stack<String>(); 11 Stack<Double> vals = new Stack<Double>(); 12 // 读取字符，若是是运算符则压入栈 13 while (!StdIn.isEmpty()) { 14 String s = StdIn.readString(); 15 if (s.equals("(")) ; 16 else if (s.equals("+")) ops.push(s); 17 else if (s.equals("-")) ops.push(s); 18 else if (s.equals("*")) ops.push(s); 19 else if (s.equals("/")) ops.push(s); 20 else if (s.equals("sqrt")) ops.push(s); 21 else if (s.equals(")")) { 22 // 若是符号为“)”, 弹出运算符和操做数，计算结果并压入栈 23 String op = ops.pop(); 24 double v = vals.pop(); 25 if (op.equals("+")) v = vals.pop() + v; 26 else if (op.equals("-")) v = vals.pop() - v; 27 else if (op.equals("*")) v = vals.pop() * v; 28 else if (op.equals("/")) v = vals.pop() / v; 29 else if (op.equals("sqrt")) v = Math.sqrt(v); 30 vals.push(v); 31 } 32 else vals.push(Double.parseDouble(s)); 33 StdOut.println("操做数栈：" + vals.toString()); 34 StdOut.println("运算符栈：" + ops.toString()); 35 } 36 StdOut.println(vals.pop()); 37 } 38 39 }
输出：
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) 操做数栈： 运算符栈： 操做数栈：1.0 运算符栈： 操做数栈：1.0 运算符栈：+ 操做数栈：1.0 运算符栈：+ 操做数栈：1.0 运算符栈：+ 操做数栈：2.0 1.0 运算符栈：+ 操做数栈：2.0 1.0 运算符栈：+ + 操做数栈：3.0 2.0 1.0 运算符栈：+ + 操做数栈：5.0 1.0 运算符栈：+ 操做数栈：5.0 1.0 运算符栈：* + 操做数栈：5.0 1.0 运算符栈：* + 操做数栈：4.0 5.0 1.0 运算符栈：* + 操做数栈：4.0 5.0 1.0 运算符栈：* * + 操做数栈：5.0 4.0 5.0 1.0 运算符栈：* * + 操做数栈：20.0 5.0 1.0 运算符栈：* + 操做数栈：100.0 1.0 运算符栈：+ 操做数栈：101.0 运算符栈：
参考资料：
算法 第四版 谢路云 译 Algorithms Fourth Edition [美] Robert Sedgewick, Kevin Wayne著
http://algs4.cs.princeton.edu/home/
源码下载连接：