双栈算术表达式求值算法

本文主要是介绍双栈算术表达式求值算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

《算法（第四版）》1.3 节在介绍背包、队列和栈时，用 Java 介绍了双栈算数表达式求值算法。现将相关内容总结如下。

比如算数表达式：

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

程序如何计算其值？我们可以用 Dijkstra 双栈算数表达式求值算法解决这个问题。编写得到的程序接受一个输入字符串（表达式）并输出表达式的值。

先给出算术表达式的递归定义：算术表达式可能是一个数，或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。

简单起见，这里定义的是未省略括号的算术表达式，而不采用优先级规则。为了突出重点，程序将仅支持最常见的二元运算符 *、+、- 和 /，以及只接受一个参数的平方根运算符 sqrt。

求值算法要用到两个栈，其求值轨迹如图 1：

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

❏将操作数压入操作数栈；

❏将运算符压入运算符栈；

❏忽略左括号；

❏在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个右括号之后，操作数栈上只会有一个值，它就是表达式的值。

要证明该过程能够计算得到正确的值很简单：每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时，它都将运算符和操作数的计算结果压入操作数栈。这样的结果就好像在输入中用这个值代替了该子表达式，因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。例如，用该算法计算以下表达式得到的结果都是相同的：

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
( 1 + ( 5 * ( 4 * 5 ) ) )
( 1 + ( 5 * 20 ) )
( 1 + 100 )
101

下面是算法实现：

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());
	}
}

简单起见，这段代码假设表达式没有省略任何括号，数字和字符均以空白字符相隔。

另，有关证明该算法正确性的更多讨论可见算法 4 中的双栈算数表达式求值算法。

这篇关于双栈算术表达式求值算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！