PHP 实现 后缀表达式

最近接触了一个有趣的需求:给定变量a、b、c、d等若干,要求由用户输入的普通四则运算字符串(包含加减乘除括号),算出具体的值。

例如,a=1,b=2,c=3,d=4,给出 a+b/(d-c),应计算出结果为3,若为 a*b/(c-1) 则应计算出结果为1

这种情况下,第一反应可能是用数字值将字符串里的变量替换,然后通过eval()执行。或者是将字符串中的每一项通过正则一个一个扣出来再进行计算。

但这样的逻辑太粗暴,代码也太丑陋,其实大可不必如此。 此时,让我们将目光移向美丽的数据结构与算法。

首先,我们了解一下 后缀表达式。

表达式一般由操作数(Operand)、运算符(Operator)组成,例如算术表达式中,通常把运算符放在两个操作数的中间,
这称为中缀表达式(Infix Expression),如A+B。我们日常生活中使用的就是此种方式
波兰数学家Jan Lukasiewicz提出了另一种数学表示法,它有两种表示形式:
把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;
把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+

我们今天要探讨的就是后缀表达式

我们如何使用它呢?

首先我们要将平时用的中缀表达式转为后缀表达式。

在此之前,我们需要一种常见的数据结构:,在这一步,我们需要两个栈,操作数栈运算符栈

1、从左至右扫描一中缀表达式。

2、若读取的是操作数,则判断该操作数的类型,并将该操作数存入操作数栈

3、若读取的是运算符

(1) 该运算符为左括号”(“,则直接存入运算符栈。

(2) 该运算符为右括号”)”,则输出运算符栈中的运算符到操作数栈,直到遇到左括号为止。

(3) 该运算符为非括号运算符:

(a) 若比运算符栈栈顶的运算符优先级高或相等,则直接存入运算符栈。
(b) 若比运算符栈栈顶的运算符优先级低,则输出栈顶运算符到操作数栈,并将当前运算符压入运算符栈。

4、当表达式读取完成后运算符栈中尚有运算符时,则依序取出运算符到操作数栈,直到运算符栈为空。

此时,将操作数栈转为一个字符串,它就是由我们输入的中缀表达式转化而来的后缀表达式

那么后缀表达式如何进行计算呢?

1、从左到右扫描后缀表达式。

2、如果扫描的项目是操作数,则将其压入操作数栈,并扫描下一个项目。

3、如果扫描的项目是一个二元运算符,则对栈的顶上两个操作数执行该运算。

4、如果扫描的项目是一个一元运算符,则对栈的最顶上操作数执行该运算。

5、将运算结果重新压入栈。

6、重复步骤2-5,直到后缀表达式扫描完毕,栈中即为结果值。


Talk is cheap,let me show you the code

接下来是使用PHP编写的这样一个工具类。可以接受传入一个表达式和表达式各项对应值 的数组,给出计算之后的结果。

使用方式:

RPNotation::calculate($exp, $exp_values);

例如:

$exp = "a+b-(c*d)/e";
$exp_values = ["a" => 1, "b" => 2, "c" => 3, "d" => 2, "e" => 3];
RPNotation::calculate($exp, $exp_values);

结果会是1


代码内容 :

<?php

//将用户输入的表达式转为逆波兰表达式计算

class RPNotation { 

    //正则表达式,用于将表达式字符串,解析为单独的运算符和操作项
    const PATTERN_EXP = '/((?:[a-zA-Z0-9_]+)|(?:[\(\)\+\-\*\/])){1}/';
    const EXP_PRIORITIES = ['+' => 1, '-' => 1, '*' => 2, '/' => 2, "(" => 0, ")" => 0];

    /*
    params:
          $exp-普通表达式,例如 a+b*(c+d)
          $exp_values-表达式对应数据内容,例如 ['a' => 1, 'b' => 2, 'c' => 3, 'd' => 4]
    */
    public static function calculate($exp, $exp_values) {
        $exp_arr = self::parse_exp($exp);//将表达式字符串解析为列表
        if (!is_array($exp_arr)) {
            return NULL;
        }
        $output_queue = self::nifix2rpn($exp_arr);
        return self::calculate_value($output_queue, $exp_values);
    }

    //将字符串中每个操作项和预算符都解析出来
    protected static function parse_exp($exp) {
        $match = [];
        preg_match_all(self::PATTERN_EXP, $exp, $match);
        if ($match) {
            return $match[0];
        }else {
            return NULL;
        }
    }

    //将中缀表达式转为后缀表达式
    protected static function nifix2rpn($input_queue){
        $exp_stack = [];
        $output_queue = [];
        foreach($input_queue as $input) {
            if (in_array($input, array_keys(self::EXP_PRIORITIES))){
                if ($input == "(") {
                    array_push($exp_stack, $input);
                    continue;
                }
                if ($input == ")") {
                    $tmp_exp = array_pop($exp_stack);
                    while ($tmp_exp && $tmp_exp != "(") {
                        array_push($output_queue, $tmp_exp);
                        $tmp_exp = array_pop($exp_stack);
                    }
                    continue;
                }
                foreach(array_reverse($exp_stack) as $exp) {
                    if (self::EXP_PRIORITIES[$input] <= self::EXP_PRIORITIES[$exp]) {
                        array_pop($exp_stack);
                        array_push($output_queue, $exp);
                    }else {
                        break;
                    }
                }
                array_push($exp_stack ,$input);
            }else {
                array_push($output_queue, $input);
            }
        }
        foreach(array_reverse($exp_stack) as $exp) {
            array_push($output_queue, $exp);
        }
        return $output_queue;
    }

    //传入后缀表达式队列、各项对应值的数组,计算出结果
    protected static function calculate_value($output_queue, $exp_values) {
        $res_stack = [];
        foreach($output_queue as $out) {
            if (in_array($out, array_keys(self::EXP_PRIORITIES))) {
                $a = array_pop($res_stack);
                $b = array_pop($res_stack);
                switch ($out) {
                    case '+':
                        $res = $b + $a;
                        break;
                    case '-':
                        $res = $b - $a;
                        break;
                    case '*':
                        $res = $b * $a;
                        break;
                    case '/':
                        $res = $b / $a;
                        break;
                    }
                array_push($res_stack, $res);
            }else {
                if (is_numeric($out)) {
                    array_push($res_stack, intval($out));
                }else {
                    array_push($res_stack, $exp_values[$out]);
                }
            }
        }
        return count($res_stack) == 1 ? $res_stack[0] : NULL;
    }

}