使用反向波兰符号（RPN）的算术表达式求值

Question

数学表达式通常用内插符号表示。出于评估目的，我们可以将其更改为后缀（反向抛光）表示法（使用像分流场这样的算法），然后使用堆栈评估后缀表示法。

我发现计算器使用这种技术，但今天的现代编译器是否使用这种技术来计算算术表达式？它是否足够有效或正在使用其他技术（或算法）？

Answer 1

为了回答这个问题，让我们关注您提到的概念，中缀符号，调车场和评估，然后将它们与编译关联起来。

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

AST用于12：

   + 
  / \ 
 1   2

后缀：1 2

这是通过访问左分支，1，
访问右分支，2，
，然后将运算符应用到两个操作数来计算的。

1*2 3^4的AST：

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

后缀：3 4^1 2*

通过访问左分支3^4，
然后访问它的左分支3，
然后访问它的右分支4，
然后访问操作符，^，然后评估3^4，并将其作为``的新左分支，即81

然后访问右分支1*2，
然后访问它的左分支1，
然后访问它的右分支2，
然后访问运算符，*，并计算1*2并保持为''的新右分支，即。2个

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

现在内缀符号是句法糖，使使用表达式更容易为人类阅读。为了帮助将内插符号转换为AST，转换算法需要知道运算符的优先级和关联性。该算法还使用了一个堆栈，这是调车场算法的主要关键之一。我所知道的将内缀转换为评估策略的每一种方法都以某种方式使用堆栈。

虽然编译器不会像计算器应用程序那样显式地对表达式求值，但编译器会将求值树的遍历转换为执行求值的代码。

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

另外，因为您提到了编译器，所以我只讨论了编译后的代码，没有涉及脚本语言。

现在回到你的问题上：

今天的现代编译器是否将其用于算术表达式求值？

我不会特别使用调车场算法，而是使用堆栈的概念，这是我将使用的算法的关键概念之一。如果使用算法的概念与使用算法相同，您可以自己选择。

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

希望你现在知道这个问题的答案。重要的不是调车场算法，而是使用堆栈转换中缀符号的概念，这是编译器使用的概念。请记住，编译语言通常不只是计算表达式，它们处理类型、处理条件表达式、存储值，并创建更高的类型，如方法/函数、类和模块。