使用反向波兰记号法（RPN）的算术表达式估计 [英] Arithmetic Expression Evaluation using Reverse Polish Notation (RPN)

问题描述

数学表达式通常以中缀表示法表示。出于评估目的，我们可以将其更改为后缀（反向抛光）符号（使用类似 Shunting-Yard ）然后使用堆栈评估后缀符号。

A mathematical expression is usually expressed in infix notation. For evaluation purposes, we can change it to postfix (reverse polish) notation (using algorithms like Shunting-Yard) and then evaluate the postfix notation using stack.

我发现计算器使用这种技术，但今天的现代编译器使用这个算术表达式求值？是否足够高效或使用其他技术（或算法）？

I found out that calculators use this technique, but do today's modern compilers use this for arithmetic expression evaluation? Is it efficient enough or other techniques (or algorithms) are being used?

推荐答案

要回答这个问题，提及中缀符号， Shunting-Yard 和评估然后将它们与编译相关联。

To answer this question let's focus on the concepts you mention, infix notation, Shunting-Yard and evaluation and then relate them to compiling.

首先，我们需要了解计算机如何处理表达式通常。表达式将转换为抽象语法树（AST），然后用于创建代码。将树转换为代码的过程各不相同，但AST的步骤与评估表达式相同。

To start with we need to understand typically how a computer processes an expression. An expression is converted to an abstract syntax tree (AST) which is then used to create the code. The process of converting the tree to code varies but a walk of the AST is the same as evaluating the expression.

AST为1 + 2：

AST for 1+2:

   + 
  / \ 
 1   2

后缀： 1 2 +

这是通过访问左侧分支 1 ，

访问正确的分支， 2 ，

，然后应用运算符 + 。

This is evaluated by visiting the left branch, 1,
the visiting the right branch, 2,
and then applying the operator, +, to the two operands.

AST为1 * 2 + 3 ^ 4：

AST for 1*2+3^4:

     + 
   /   \
  ^     *
 / \   / \
3   4 1   2

后缀： 3 4 ^ 1 2 * +

这是由
访问左侧分支 3 ^ 4 ，

然后访问它的左侧分支 3 ，

然后访问它的右分支 4 ，

然后访问操作员， ^ ，
并评估 3 ^ 4 ，并将其作为'+'的新左分支，即81

This is evaluated by visiting the left branch 3^4,
then visiting it's left branch 3,
then visiting it's right branch 4,
then visiting the operator, ^, and evaluating 3^4 and holding that as the new left branch for `+', i.e. 81

然后访问右侧分支 1 * 2 ，

然后访问它的左侧分支 1 ，

然后访问它的右分支 2 ，

然后访问操作符 * ，
并评估 1 * 2 +，即2

then visiting the right branch 1*2,
then visiting it's left branch 1,
then visiting it's right branch 2,
then visiting the operator, *, and evaluating 1*2 and holding that as the new right branch for `+', i.e. 2

然后访问运算符 + ，
并评估 81 + 2 并返回结果 83

then visiting the operator, +, and evaluating 81+2 and returning that as the result 83

是语法糖，使用表达式更容易为人类阅读。为了帮助将中缀符号转换为AST，转换算法需要知道优先级和社群性。该算法还使用堆栈，这是Shunting-Yard算法的主要密钥之一。我知道将infix转换为一个评估策略在某种程度上使用堆栈。我们知道的每一种方法。

Now infix notation is syntactic sugar to make using expressions easier to read for humans. In order to help convert infix-notation to an AST, the conversion algorithm needs to know the precedence and associativity of the operators. The algorithm also uses a stack which is one of the main keys to the Shunting-Yard algorithm. Every means I know of to convert infix to an evaluation strategy uses a stack in some way.

虽然编译器没有显式计算表达式，应用程序，编译器会将用于评估的树的行走转换为将执行评估的代码。

While a compiler does not explicitly evaluate an expression as can be done with a calculator application, the compiler does convert the walking of the tree for evaluation into code that will preform the evaluation.

注意：由于我不知道每种语言的每个编译器，我只能给你一个基于一般概念的答案。没有规则需要遵循这些规则，如果一些编译器跳过AST并且从输入代码转换为使用AST的编译代码，我不会感到惊讶。

Note: Since I do not know every compiler for every language, I can only give you an answer based on general concepts. There is no rule that requires these be followed and I would not be surprised if some compilers skip the AST and go from the input code to compiled code with out using AST.

因为你提到一个编译器，我只谈到编译代码，没有触及脚本语言。

Also since you mention a compiler I only talked about compiled code and did not touch on scripting languages.

现在回到你的问题：

今天的现代编译器使用这个算术表达式
求值吗？

Do today's modern compilers use this for arithmetic expression evaluation?

我不会特别使用Shunting-Yard算法，而是使用堆栈的概念，这是我将使用的算法的关键概念之一。

I would not specifically use the Shunting-Yard algorithm but the concepts of using a stack which is one of the key concepts of the algorithm I would be using. You can chose for yourself if using the concepts of algorithm is the same as using the algorithm.

它是否足够高效或其他技术算法）正在使用
？

Is it efficient enough or other techniques (or algorithms) are being used?

希望现在你知道这个问题的答案。它不是Shunting-Yard算法是重要的，但使用堆栈来翻译中缀符号的概念是重要的，这是与编译器使用。请记住，编译语言通常不仅仅评估表达式，它们处理类型，处理条件表达式，存储值，以及创建更高的类型，例如方法/函数，类和模块。

Hopefully by now you know the answer to this question. It is not the Shunting-Yard algorithm that is important but the concept of using the stack to translate infix-notation that is important and that is what is used with compilers. Remember that compiled languages typically do more than evaluate expressions, they work with types, process conditional expression, store values, and create higher types such as methods/functions, classes, and modules.

这篇关于使用反向波兰记号法（RPN）的算术表达式估计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！