关于调车场的基本问题

Question

我已经完成了Shunting-yard算法的实现，但有一些问题：

1. 该算法如何验证输入是否合法，换句话说，它如何检测a++b是否合法(确定不是合法的)
2. 第二步我应该做什么？调车场将1+2转换为1 2 +

关于1：更新：

经过一些尝试后，我认为是这样做的，例如，以a++b为例，当我计算它时，我会取一个a+b+ +，但是由于我手头只有一个变量，所以这是一个错误。

对于非有效表达式，总是这样吗？

Answer 1

1.语法错误

这取决于你如何准确地实现算法，但在通常由互联网搜索发现的版本中，并不能保证一个不符合语法的表达式会被分流场算法正确地拒绝。许多不正确的表达式会产生不正确的后缀字符串(正如您注意到的那样)，甚至会产生正确的后缀字符串。特别是，如果您有一元运算符，则算法(通常会出现)不能真正区分前缀使用，即操作符在操作数前面，或者后缀使用，其中操作符跟随操作数。

如果目标语言的操作符可以用作前缀或后缀操作符，具有不同的语义(例如C系列的++和--操作符)，那么这将是一个严重的问题。由于算法没有区分这两种情况，因此失去了语义上的差异。

运算符有一个类似的、更常见的问题，可以用作二进制infix运算符，也可以用作前缀运算符，例如-运算符。除非区分这两个用途，否则后缀输出将无法解释，因为当到达-时，评估器无法知道它是应用于一个操作数还是两个操作数。(此外，一元减号运算符很可能是以不正确的优先级处理的，因为一元减号的期望优先级高于乘法和除法。但是，对于大多数算术表达式，使用不正确的优先级不会更改结果的数值，因为-(x * y)和(-x) * y的值完全相同。如果您实现了一个模运算符，结果将是不正确的。)

分流场算法将检测不平衡括号，因为不平衡括号将导致解析堆栈被溢出，或者在解析结束时有太多的值。

用一个非常小的状态机对分流场算法进行扩充相对容易，该机器足以对具有多个句法意义的操作符的不同明确使用进行分类；该状态机还足以检测上述其他语法错误:运算符的位置不正确，或者完全丢失。

由于在实际应用中需要正确区分一元否定和二进制否定，前缀和后缀操作符的不同含义，以及括号的不同用法(分组和函数调用)，使用分流场的产生分析器将包含一些额外的句法机制，同时也会检测语法错误。这种算法的一个例子是在这个答案中。

2. RPN作为中间步骤

绝对没有必要使用RPN作为中间结果；分流场算法可用于

• 直接计算算术表达式(如果表达式不包括条件结构或循环结构)，
• 输出堆栈机器编译器的可执行代码(或者，用更多的精力为更真实的机器输出三地址代码)，或者更一般地输出。
• 生成表示解析表达式的语法树，该表达式可用于上述任何目的和其他语义分析任务。

要生成语法树，需要将操作数推到解析器堆栈上，而不是直接将它们输出到输出流。此外，当您将运算符推到堆栈上时，实际上是推表示该运算符应用程序的语法节点:对于二进制运算符，它与前两个堆栈槽组合在一起。(对于一个一元操作符来说，它的顶部是堆栈槽。)如果要使用分流场作为直接评估器，则使用相同的策略，但将运算符推到堆栈上会导致以相同方式标识的操作数对该运算符的计算。

RPN中间表示实际上没有提供任何价值。我不知道为什么它这么受欢迎。

Answer 2

看看我能不能帮你把它拆开。分流码算法通过打破一个注解来执行以下操作之一：

1. 要么生成一个后缀符号字符串(也称为反向波兰符号)
2. 或者抽象语法树。

在你的例子中，它是后缀符号。

[注意:我希望您了解后缀符号，如果不是，请阅读这。]

现在，后缀符号使计算数学表达式变得非常容易。我将向您展示如何计算后缀符号：

In a simple description:
    (1) Infix: A + B
        Postfix: A B +
    (2) Infix: A + B * C
        Postfix: A B C * +

Let's observe the part A+B*C i.e. A+(B*C)

If we represent it in Postfix, it would be like: A B C * +(by applying shunting-yard)

Now, the algorithm to calculate it
    (1) Take a stack
    (2) When we see a number, we push it to stack
    (3) When we see a operator, we pop two numbers out of stack and calculate them with help of operator and push the result into stack again
    (4) We do it till the end
    (5) At last, only a number would be left in stack, that is our answer.

Let's visualise it:
    (1) [A]
    (2) [A, B]
    (3) [A, B, C]
    (4) [A, R1] where R1 = B*C
    (5) [R2] where R2 = A+R1

我希望，你已经明白了，调车场将帮助你转换为后缀，然后，你可以很容易地评估后缀符号。

现在的问题是如何检测a++b 错误。

现在，观察a，+，+，b令牌发生了什么(正如您在注释中所述：a++b被标记为a，+，+，b令牌)：

我从维基百科获得了伪代码(变得懒惰，不想自己写)：

else if the token is an operator then:
        while ((there is a operator at the top of the operator stack)
              and ((the operator at the top of the operator stack has greater precedence)
               or (the operator at the top of the operator stack has equal precedence and the token is left associative))
              and (the operator at the top of the operator stack is not a left parenthesis)):
            pop operators from the operator stack onto the output queue.
        push it onto the operator stack.

基于这一点: a，+，+，b将在输出队列中采取以下形式：

a, b, +, +

a, b, +, +只是简单的错误，因为根据后缀评估规则，会发生以下情况：

1. [a] // output queue is now [b, +, +]
2. [a, b] // output queue is now [+, +]
3. [r1] // output queue is now [+]
4. error // cause: notice there's still one '+' operator left in queue
// but, only one number 'r1' left in the 'stack'
// so, error

我希望你现在明白了..。