表达式算法php（表达算法的两种方法）

在PHP中，有两种常见的表达式计算算法：逆波兰表达式算法和中缀表达式算法。

1. 逆波兰表达式算法（Reverse Polish Notation, RPN）： 逆波兰表达式是一种不需要括号来区分优先级的表达式表示方法。在逆波兰表达式中，操作符位于操作数之后，因此可以通过栈来计算表达式的值。

逆波兰表达式的计算步骤：

• 创建一个空栈。
• 从左到右遍历表达式的每个元素。
• 如果遇到操作数，则将其入栈。
• 如果遇到操作符，则从栈中弹出两个操作数进行计算，并将结果入栈。
• 最后栈中只剩下一个元素，即为表达式的计算结果。

示例代码：

function evaluateRPN($expression) {
    $stack = [];
    $operators = ['+', '-', '*', '/'];

    foreach ($expression as $token) {
        if (is_numeric($token)) {
            array_push($stack, $token);
        } else if (in_array($token, $operators)) {
            $operand2 = array_pop($stack);
            $operand1 = array_pop($stack);

            switch ($token) {
                case '+':
                    array_push($stack, $operand1 + $operand2);
                    break;
                case '-':
                    array_push($stack, $operand1 - $operand2);
                    break;
                case '*':
                    array_push($stack, $operand1 * $operand2);
                    break;
                case '/':
                    array_push($stack, $operand1 / $operand2);
                    break;
            }
        }
    }

    return array_pop($stack);
}

$expression = [5, 3, '+', 2, '*'];
$result = evaluateRPN($expression);
echo $result; // 输出 16

2. 中缀表达式算法： 中缀表达式是我们通常所见的常规表达式，例如 "5 + 3 * 2"。中缀表达式的计算需要考虑运算符的优先级和括号的影响。

中缀表达式的计算步骤：

• 创建一个空栈和一个空队列。
• 从左到右遍历表达式的每个元素。
• 如果遇到操作数，则将其加入队列。
• 如果遇到运算符，则与栈顶的运算符进行比较：
  • 如果栈为空或栈顶为左括号，则将运算符入栈。
  • 如果栈顶为右括号，则将栈顶的运算符弹出并加入队列，直到遇到左括号或栈为空。
  • 如果栈顶为其他运算符，并且栈顶运算符的优先级大于当前运算符，则将栈顶运算符弹出并加入队列，直到栈为空或栈顶运算符的优先级小于等于当前运算符。
  • 将当前运算符入栈。
• 如果遇到左括号，则将其入栈。
• 如果遇到右括号，则将栈顶的运算符弹出并加入队列，直到遇到左括号。
• 遍历完表达式后，将栈中剩余的运算符弹出并加入队列。
• 最后对队列中的元素进行计算，得到表达式的结果。

示例代码：

function evaluateInfix($expression) {
    $stack = [];
    $queue = [];
    $operators = ['+', '-', '*', '/'];

    foreach ($expression as $token) {
        if (is_numeric($token)) {
            array_push($queue, $token);
        } else if ($token == '(') {
            array_push($stack, $token);
        } else if ($token == ')') {
            while (end($stack) != '(') {
                array_push($queue, array_pop($stack));
            }
            array_pop($stack); // 弹出左括号
        } else if (in_array($token, $operators)) {
            while (!empty($stack) && end($stack) != '(' && getPriority(end($stack)) >= getPriority($token)) {
                array_push($queue, array_pop($stack));
            }
            array_push($stack, $token);
        }
    }

    while (!empty($stack)) {
        array_push($queue, array_pop($stack));
    }

    foreach ($queue as $token) {
        if (is_numeric($token)) {
            array_push($stack, $token);
        } else if (in_array($token, $operators)) {
            $operand2 = array_pop($stack);
            $operand1 = array_pop($stack);

            switch ($token) {
                case '+':
                    array_push($stack, $operand1 + $operand2);
                    break;
                case '-':
                    array_push($stack, $operand1 - $operand2);
                    break;
                case '*':
                    array_push($stack, $operand1 * $operand2);
                    break;
                case '/':
                    array_push($stack, $operand1 / $operand2);
                    break;
            }
        }
    }

    return array_pop($stack);
}

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

$expression = [5, '+', 3, '*', 2];
$result = evaluateInfix($expression);
echo $result; // 输出 11

以上是两种常见的表达式算法在PHP中的实现方法。根据实际需求选择适合的算法来计算表达式。