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

用 PHP 创建计算器

简化输入到 中的数学表达式PHP 中的标签可能具有挑战性，尤其是在保留原始符号时。虽然用计算值替换字符串的暴力方法最初似乎可行，但效率很低。

利用 Shunting Yard 算法

更有效的解决方案是 Shunting码算法。它将输入表达式转换为逆波兰表示法 (RPN)。 RPN 简化了计算，因为操作数后紧跟其运算符。

实现示例

以下代码提供了 PHP 中调车场算法的实现：

class Expression {

    protected $tokens;
    protected $output;

    // Shunting Yard Algorithm
    public function shuntingYard($input) {
        $stack = [];
        $tokens = $this->tokenize($input);
        foreach ($tokens as $token) {
            if (is_numeric($token)) {
                $this->output[] = $token;
            } else {
                switch ($token) {
                    case '(':
                        $stack[] = $token;
                        break;
                    case ')':
                        while ($stack && end($stack) != '(') {
                            $this->output[] = array_pop($stack);
                        }
                        if (!empty($stack)) {
                            array_pop($stack);
                        }
                        break;
                    default:
                        while ($stack && $this->precedence($token) <= $this->precedence(end($stack))) {
                            $this->output[] = array_pop($stack);
                        }
                        $stack[] = $token;
                        break;
                }
            }
        }
        while (!empty($stack)) {
            $this->output[] = array_pop($stack);
        }
    }

    // Tokenize the input
    public function tokenize($input) {
        preg_match_all('~\d+|~|~U', $input, $tokens);
        return $tokens[0];
    }

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

    // Evaluate the RPN expression
    public function evaluate() {
        $stack = [];
        foreach ($this->output as $token) {
            if (is_numeric($token)) {
                $stack[] = $token;
            } else {
                $operand2 = array_pop($stack);
                $operand1 = array_pop($stack);
                switch ($token) {
                    case '+':
                        $result = $operand1 + $operand2;
                        break;
                    case '-':
                        $result = $operand1 - $operand2;
                        break;
                    case '*':
                        $result = $operand1 * $operand2;
                        break;
                    case '/':
                        $result = $operand1 / $operand2;
                        break;
                }
                $stack[] = $result;
            }
        }
        return array_pop($stack);
    }
}

$expression = new Expression();
$expression->shuntingYard('8*(5+1)');
$result = $expression->evaluate();

echo $result; // Output: 48

此代码将输入转换为 RPN，评估结果堆栈，并返回最终结果结果。

以上是调车场算法如何简化 PHP 中的数学表达式求值？的详细内容。更多信息请关注PHP中文网其他相关文章！