algorithm - 修改调车场算法以包含墙运算符 |

Question

标准如何Shunting Yard Algorithm修改为包含一个“墙”符号|，表示函数参数的结尾？也就是说，支持修改后缀表示法(Reverse Polish Notation)，允许具有任意数量参数的函数。

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

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

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

调车场算法

1. 当有 token 要读取时:
2. 读取 token 。
3. 如果 token 是数字，则将其推送到输出队列。
4. 如果 token 是函数 token ，则将其压入堆栈。
5. 如果标记是函数参数分隔符(例如逗号):
   • 直到堆栈顶部的标记为左括号，将运算符从堆栈中弹出到输出队列中。如果没有遇到左括号，则说明分隔符放错了位置或括号不匹配。

6. 如果 token 是运算符 o1，则:

   • 虽然有一个运算符 token o2，但在运算符堆栈的顶部，或者

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

     • o1 是右结合的，并且优先级低于 o2，

       -将o2从操作栈中弹出，放到输出队列中；

     • 在迭代结束时将 o1 压入运算符堆栈。
7. 如果 token 是左括号(即“(”)，则将其压入堆栈。
8. 如果标记是右括号(即“)”):
   • 直到堆栈顶部的标记为左括号，将堆栈中的运算符弹出到输出队列中。
   • 将左括号从栈中弹出，但不进入输出队列。
   • 如果栈顶的 token 是函数 token ，将其弹出到输出队列。
   • 如果堆栈用完而没有找到左括号，则存在不匹配的括号。
9. 当没有更多的标记可读时:
   • 当堆栈中仍有运算符标记时:
     • 如果堆栈顶部的运算符标记是括号，则存在不匹配的括号。
     • 将运算符弹出到输出队列。
10. 退出。

Answer 1

解决方法:

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

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