调车场算法如何简化 PHP 中的数学表达式求值？

调车场算法（Shunting Yard Algorithm） 是一种用于将中缀表达式转换为后缀表达式（也叫逆波兰表示法, RPN）的算法，旨在简化数学表达式的求值。它由计算机科学家 埃德加·唐纳德·霍普克罗夫特（Edgar Dijkstra）提出，原本用于解析数学表达式。该算法可以有效地处理运算符优先级和括号等问题，最终得出一个可以直接求值的后缀表达式。

在 PHP 中，利用调车场算法可以简化数学表达式的求值，特别是当涉及复杂运算符和括号时，传统的中缀表达式（例如 3 + 5 * (2 - 8)）会变得不易处理，而将其转换为后缀表达式可以直接进行计算。

调车场算法的步骤概述

1. 输入：中缀表达式（例如：3 + 5 * (2 - 8)）。
2. 输出：后缀表达式（例如：3 5 2 8 - * +）。
3. 操作：
   • 使用一个栈存储运算符和左括号。
   • 从左至右扫描中缀表达式的每个字符：
     • 如果是操作数（数字），直接输出。
     • 如果是左括号，将其压入栈中。
     • 如果是右括号，弹出栈内所有运算符直到遇到左括号。
     • 如果是运算符（+, -, *, / 等），则弹出栈内优先级高于或等于当前运算符的运算符，直到栈内运算符的优先级低于当前运算符，然后将当前运算符压入栈中。
4. 输出后缀表达式：遍历完成后，栈中剩余的运算符按顺序输出。

后缀表达式求值

后缀表达式的求值可以通过一个栈来完成：

• 遇到操作数，将其压入栈中。
• 遇到运算符，从栈中弹出两个操作数，进行运算，然后将结果压回栈中。
• 最终，栈中剩下的唯一元素即为表达式的结果。

PHP 中实现调车场算法的代码示例

1. 转换中缀表达式为后缀表达式

function precedence($operator) {
    switch ($operator) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return 0;
    }
}

function infixToPostfix($expression) {
    $stack = [];
    $output = [];
    $tokens = preg_split('/(\d+|[-+*\/\^\(\)])/s', $expression, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);

    foreach ($tokens as $token) {
        if (is_numeric($token)) {
            // 如果是数字，直接添加到输出
            $output[] = $token;
        } elseif ($token === '(') {
            // 左括号，压入栈
            array_push($stack, $token);
        } elseif ($token === ')') {
            // 右括号，弹出栈直到遇到左括号
            while (!empty($stack) && end($stack) !== '(') {
                $output[] = array_pop($stack);
            }
            array_pop($stack); // 弹出左括号
        } else {
            // 运算符
            while (!empty($stack) && precedence(end($stack)) >= precedence($token)) {
                $output[] = array_pop($stack);
            }
            array_push($stack, $token);
        }
    }

    // 将栈中剩余的运算符添加到输出
    while (!empty($stack)) {
        $output[] = array_pop($stack);
    }

    return implode(' ', $output); // 返回后缀表达式
}

// 示例：转换中缀表达式为后缀表达式
$infix = "3 + 5 * (2 - 8)";
$postfix = infixToPostfix($infix);
echo "后缀表达式: $postfix"; // 输出 "3 5 2 8 - * +"

2. 求值后缀表达式

function evaluatePostfix($postfix) {
    $stack = [];
    $tokens = explode(' ', $postfix);

    foreach ($tokens as $token) {
        if (is_numeric($token)) {
            // 如果是数字，压入栈
            array_push($stack, $token);
        } else {
            // 否则，运算符，弹出栈内两个操作数并计算结果
            $b = array_pop($stack);
            $a = array_pop($stack);
            switch ($token) {
                case '+':
                    array_push($stack, $a + $b);
                    break;
                case '-':
                    array_push($stack, $a - $b);
                    break;
                case '*':
                    array_push($stack, $a * $b);
                    break;
                case '/':
                    array_push($stack, $a / $b);
                    break;
                case '^':
                    array_push($stack, pow($a, $b));
                    break;
            }
        }
    }

    // 栈中的唯一元素即为结果
    return array_pop($stack);
}

// 示例：求值后缀表达式
$result = evaluatePostfix($postfix);
echo "结果: $result"; // 输出结果 "结果: -13"

总结

1. 调车场算法将中缀表达式转换为后缀表达式，使得运算符的优先级和括号不再需要额外处理，可以直接进行计算。
2. 使用后缀表达式求值时，可以通过栈实现，避免了括号和优先级的干扰，计算过程更加简洁和高效。
3. 在 PHP 中实现时，通过将表达式拆分为字符（如数字和运算符），可以灵活地处理复杂的数学表达式。
4. 结合调车场算法和栈求值的方法，可以有效简化表达式的求值过程，特别是在处理复杂的中缀表达式时。

这种算法适用于需要高效解析和计算数学表达式的场景，如计算器、表达式求值系统等。