扩展分流场算法以支持条件三元运算符

Question

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

Answer 1

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

• "？" 三元开频
• "：" 三元-否则
• 三元闭合中频

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

示例（三元闭合 - 如果标记为"？："）：

• "一？b ： c" -->
  "A B C ？："
• "一？B ： x ？y ： z" -->
  "A B X Y Z ？： ？："
• "一？x ?y ： z ： b" -->
  "A X Y Z ？： 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     |
+-------+------------------------------------------------------------------------------------------+-------+

Answer 3

遇到

： token 后递归调用调车场函数，如

token_array shunting_yard(token_stream input)
{
    // assuming its working shunting yard algorithm that works correctly
    // on all unary/binary operators and know how to deal with parenthesis
    if(input.peek().token_type == ?)
    {
        operators_stack.push(?);
        input.seek(til next token);
    }
    // whatever was between ? and : was parsed somewhere above
    if(input.peek().token_type == :)
    {
        input.seek(til next token);
        // recursively call this function
        token_array ret_arr = shunting_yard(input);
        operands_stack = merge two stacks together(operators_stack, ret_array);
        operands_stack.push(operators_stack.pop()) <- should move ?
        input.seek(til next token);
    }
    // important bit
    if(unpaired ')' detected)
    {
        while(operators_stack.size > 0)
            operands_stack.push(operators_stack.pop());
        return operands_stack;
    }
}

论证：

以表达式 a+b-c？d：e+f 和 a+b-（c？d：e）+f 为例

案例 A+B-C？D：E+F
它有问题，因为三元运算符将其计算为 （a+b-c）？（d）:(e+f），这绝对不是本意，但它仍然是一个有效的三元表达式。GCC，Node，Firefox，Chrome，Edge和.NET至少像这样评估它。我是谁来挑战边缘控制台的计算能力???调车场，当到达时：令牌应该有操作数和运算符堆栈看起来像
操作数 a， b， +， c， -， d
运算符 ？
shunting_yard的递归调用返回数组 e， f， +
将返回的数组连接到操作数堆栈
操作数 a， b， +， c， -， d， e， f， +
运算符 ？
最后
堆栈 A， B， +， C， -， D， E， F， +， ？
评估它以检查它是否返回相同的结果

a , b , + == a+b, assign result to variable called o1, for short  
o1, c, - == o1 - c == (a + b) - c, assign result to o2  
o2, d, e, f, + == (a + b - c), d, (e + f), assign result to o3  
o2, d, o3, ?, which evaluates as o2?d:o3, which, after variables substitution is the original expression a + b - c ? d : e + f (first operand is condition, second is 'on true' returns, third is 'on false' returns, same below)  

案例 A+B-（C？D：E）+F
调车场，当到达时：令牌应该有操作数和运算符堆栈看起来像
操作数 a， b， +， c， d
运算符 -, ?
shunting_yard的递归调用返回数组（来自单个元素）e
将返回的数组连接到操作数堆栈
操作数 a， b， +， c， d， e
运算符 -, ?
现在移动 ？
操作数 a， b， +， c， d， e， ？
运算符 -
像往常一样继续解析，get
堆栈 A， B， +， C， D， E， ？-， f， +
评价

a , b , + == a+b, assign result to o1  
o1, c, d, e, ? == o1, (c?d:e), assign result of ternary operation to o2  
o1, o2, - == o1 - o2 == a + b - (d or e, depending of value of c), assign result to o3  
o3, f, + == o3 + f which after variables substitution is the original expression is the original expression a + b - (d or e, depending of value of c) + f

其他运算符以相同的方式工作，如果它们（运算符）具有与此处所述的相同优先级
https://en.cppreference.com/w/cpp/language/operator_precedence嵌套三元，虽然绝对是一个糟糕的设计，但也支持。