2

如何修改标准的调车场算法以包含一个“墙”符号 |,表示函数参数的结束?也就是说,支持修改后缀表示法(反向波兰表示法),它允许函数具有任意数量的参数。

修改后缀表示法的几个示例:

f (1,2)+9 ⟶ | 1 2 f 9 +
f (1,2,3)+9 ⟶ | 1 2 3 9 +

拜托,我正在寻找实际的修改,而不仅仅是关于如何做的想法。

调车场算法

  1. 虽然有要读取的令牌:
  2. 读取令牌。
  3. 如果令牌是数字,则将其推送到输出队列。
  4. 如果令牌是函数令牌,则将其压入堆栈。
  5. 如果标记是函数参数分隔符(例如,逗号):
    • 直到堆栈顶部的标记是左括号,将操作符从堆栈中弹出到输出队列中。如果没有遇到左括号,则分隔符放错位置或括号不匹配。
  6. 如果令牌是运算符 o1,则:

    • 虽然有一个操作员令牌 o2,但在操作员堆栈的顶部,或者

      • o1 是左结合的,它的优先级小于或等于 o2 的优先级,或者
      • o1 是右结合的,并且优先级低于 o2,

        -pop o2 从算子栈中弹出到输出队列中;

      • 在迭代结束时,将 o1 推入运算符堆栈。
  7. 如果令牌是左括号(即“(”),则将其压入堆栈。
  8. 如果标记是右括号(即“)”):
    • 直到堆栈顶部的标记是左括号,将操作符从堆栈中弹出到输出队列中。
    • 从堆栈中弹出左括号,但不在输出队列中。
    • 如果堆栈顶部的令牌是函数令牌,则将其弹出到输出队列中。
    • 如果堆栈用完而没有找到左括号,则存在不匹配的括号。
  9. 当没有更多要读取的令牌时:
    • 虽然堆栈中仍有操作符标记:
      • 如果栈顶的操作符记号是括号,则括号不匹配。
      • 将操作员弹出到输出队列中。
  10. 出口。
4

1 回答 1

1

解决方案:

在步骤 4 中,除了将函数压入堆栈之外,还要编写 | 输出后缀表达式的符号。

当然,评估这个修改后的后缀表达式的算法本身必须修改以考虑墙壁符号。

于 2017-03-09T00:30:01.940 回答