提问者:小点点

调车场算法,有什么变化吗?


我已经按照维基百科里提到的,用C++11实现了调车场算法:

此实现不实现复合函数,参数数目可变的函数和一元运算符。

while there are tokens to be read:
    read a token.
    if the token is a number, then:
        push it to the output queue.
    else if the token is a function then:
        push it onto the operator stack 
    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.
    else if the token is a left parenthesis (i.e. "("), then:
        push it onto the operator stack.
    else if the token is a right parenthesis (i.e. ")"), then:
        while the operator at the top of the operator stack is not a left parenthesis:
            pop the operator from the operator stack onto the output queue.
        /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
        if there is a left parenthesis at the top of the operator stack, then:
            pop the operator from the operator stack and discard it
/* After while loop, if operator stack not null, pop everything to output queue */
if there are no more tokens to read then:
    while there are still operator tokens on the stack:
        /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
        pop the operator from the operator stack onto the output queue.
exit.

正如您所看到的,上面提到的,这个算法不处理一元运算符,假设我有一个,它比所有其他运算符都强,如果有的话,我应该对我的算法做什么修改呢?

使用运算符的一些合法示例:

!1
! 1
! (1)
!(  1 + 2)

再加上一个小问题,这个算法能处理像1==2这样的错误语法吗(我认为是的)?


共1个答案

匿名用户

问题1:

为了使您的算法正常工作,您应该在中缀运算符之前解析前缀运算符,简单地将其视为一个开括号((然后您需要调整堆栈虚拟机以允许这种运算符)。 我建议将圆括号的if检查移到中缀运算符之前(变化不大,但更易读)。 我还要说,如果您想同时实现运算符优先级,后缀运算符和mixfix运算符之类的功能,您应该切换到Pratt解析器(它更容易使用)。

问题2:

这里的解析器不处理像1==2这样的操作,它只解析它们。 基于堆栈的虚拟机处理它们,1==2是一个非常好的比较,因为它应该返回false。 如果您计划使用布尔表达式和算术表达式,则使用此选项。