栈和队列表达式求值

栈和队列是计算机科学中常用的数据结构，常用于表达式求值，其中栈和队列都有着重要的作用。在表达式求值中，个人经验和一些书籍中介绍的做法差异很大，本文将从多个角度分析栈和队列表达式求值，旨在帮助读者更好地理解这个问题。

首先，我们需要知道什么是表达式。表达式(Expression)是指用运算符和运算数等操作元素按一定规律排列起来的式子。在计算机中，表达式通常是一条算术或者逻辑语句。例如，在终端输入2 + 3 * 4，使用表达式求值，得到2 + 12 = 14。在这个例子中，2，3和4是操作数，+和*是运算符。

方法一：递归调用。

递归调用是一种常用的方法，特别是在树形结构中。对于表达式求值，递归调用可以用来将表达式分为更小的子表达式。例如，对于表达式2+3*4，我们可以将其分解为2和3*4的子表达式，然后将3*4分解为3和4子表达式，然后再计算子表达式的值。最后，我们可以使用递归调用的方法将子表达式的值组合起来，得到表达式的结果14。

递归调用的优点是程序简洁明了，易于理解。但是在表达式求值中，效率不高。

方法二：使用栈

栈是一种后进先出的数据结构，对于表达式求值有很好的应用。我们可以使用两个栈，一个操作数栈和一个操作符栈。当遇到操作符时，将其压入操作符栈中，当遇到操作数时，将其压入操作数栈中。在遇到当前运算符优先级小于等于上一个运算符的优先级时，从栈中取出两个操作数和一个操作符进行计算，并将计算结果压入操作数栈中。直到整个表达式计算完成，最后栈中只剩下一个操作数，即为表达式的结果。

例如：假设有表达式2+3*4-5，当从左到右依次扫描表达式，遇到数字2，将其压入操作数栈中。接着遇到运算符+，将其压入操作符栈中。遇到数字3，将其压入操作数栈中。遇到运算符*，由于*的优先级大于+，因此将其压入操作符栈中。遇到数字4，将其压入操作数栈中。由于此时操作符栈顶是*，因此从操作数栈中取出3和4，并取出*进行计算，将其结果12压入操作数栈中。最后，遇到运算符-，将其压入操作符栈中。遇到数字5，将其压入操作数栈中。由于表达式结束，因此从操作数栈中取出2和12，并取出+进行计算，然后再从操作数栈中取出5，并取出-进行计算，得到表达式的结果9。

方法三：使用队列

队列是一种先进先出的数据结构，在表达式求值中可以使用两个队列实现。我们可以先将中缀表达式转换成后缀表达式，然后将其依次入队到操作数队列中，再依次从队列中取出操作数和操作符进行计算，最后得到表达式的结果。

例如：假设有中缀表达式2+3*4-5，将其转换为后缀表达式为234*+5-。当依次将其入队到操作数队列中，队列过程为：2->3->4->*->+->5->-。然后依次从队列中取出操作数和操作符进行计算。当取出4和*时，计算结果为12，将其重新入队，队列状态为：2->3->12->+->5->-。当取出3和+时，计算结果为15，将其重新入队，队列状态为：2->15->5->-。当取出5和-时，计算结果为10，最终得到表达式的结果为10。

综上所述，本文介绍了三种常用的表达式求值方法：递归调用、使用栈、使用队列。对于中小规模数据，递归调用和使用栈均可以快速求值，而使用队列更适用于大规模数据求值。然而，这三种方法相比于现代计算机处理器的性能，都较为低效。因此，算法的复杂度和优化成为当前求解表达式问题的研究方向。

【关键词】栈、队列、表达式求值。