ternary-operator - 扩展调车场算法以支持条件三元运算符

Question

如何扩展调车场算法，这原本是为了让二元运算符支持条件三元运算符（“a？b：c”）？我还没有在这里看到这个问题的答案，我有一个，所以我发布它。

Answer 1

我这样做的方法是添加三个新的运算符：

• “？” 三元开放式
• ":" 三元-else
• 三元封闭-if

读取初始表达式时，只会直接创建前两个。
但是，只有第三个将存在于输出中（初始表达式的 RPN）。
每当一个“？可见。
ternary-else 永远不会放入堆栈。相反，堆栈被弹出，直到找到一个三元开放-if，然后三元开放-if被替换为三元闭合-if（因此表明我们在条件运算符的else部分）。
所有三个运算符的优先级都高于所有其他运算符（更高意味着它们在其他运算符之后进行评估）。
三元-if 运算符具有相同的优先级和右结合性（就像在 C 中一样），这意味着三元-if 永远不会导致另一个三元-if 的弹出。
ternary-else 的优先级高于 ternary-ifs，并且它的关联性是无关紧要的（因为它从未放入堆栈）。因此，当遇到三元开放时，它会如前所述将其转换为封闭的。
当遇到一个三元-封闭-如果它会弹出它。

示例（三元封闭，如果表示为“？：”）：

• "a ? b : c" -->
  "abc ?:"
• "a ? b : x ? y : z" -->
  "abxyz ?: ?:"
• "a ? x ? y : z : b" -->
  "axyz ?: b ?:"

这种方法解释起来比实现起来更难，而且它确实对算法做了一点改动，所以如果有人有更简单的解决方案，请发布。

Answer 2

对于仍在此处搜索的任何人，条件三元运算符也可以实现为具有三个参数的 IF 函数：

IF([boolean], [expr_if_true], [expr_if_false])

例如，要IF(5 > 4, 9, 8)通过扩展调车场算法转换为逆波兰表示法，请执行以下操作：

+-------+---------------------------------------------------+--------------+----------------+
| Token | Action                                            | RPN Output   | Operator stack |
+-------+---------------------------------------------------+--------------+----------------+
| IF    | Push token to stack                               |              | IF             |
| (     | Push token to stack                               |              | IF (           |
| 5     | Add token to output                               | 5            | IF (           |
| >     | Push token to stack                               | 5            | 15 ( >         |
| 4     | Add token to output                               | 5 4          | IF ( >         |
| ,     | Pop from stack onto output until left parenthesis | 5 4 >        | IF (           |
| 9     | Add token to output                               | 5 4 > 9      | IF (           |
| ,     | Pop from stack onto output until left parenthesis | 5 4 > 9      | IF (           |
| 8     | Add token to output                               | 5 4 > 9 8    | IF (           |
| )     | Pop from stack onto output until left parenthesis | 5 4 > 9 8    | IF             |
| end   | Pop entire stack onto output                      | 5 4 > 9 8 IF |                |
+-------+---------------------------------------------------+--------------+----------------+

后缀被评估为：

+-------+------------------------------------------------------------------------------------------+-------+
| Token | Action                                                                                   | Stack |
+-------+------------------------------------------------------------------------------------------+-------+
| 5     | Push to stack                                                                            | 5     |
| 4     | Push to stack                                                                            | 4     |
| >     | Pop from stack twice (5, 4), evaluate (5 > 4) and push onto stack                        | TRUE  |
| 9     | Push onto stack                                                                          | 9     |
| 8     | Push onto stack                                                                          | 8     |
| IF    | Pop from stack thrice (TRUE, 9, 8), evaluate (IF TRUE THEN 9 ELSE 8) and push onto stack | 9     |
+-------+------------------------------------------------------------------------------------------+-------+