【数据结构】栈的应用---四则运算表达式求值（中缀表达式与后缀表达式转换）

￡神魔★判官ぃ 2022-06-15 23:25 242阅读 0赞

用计算机实现带括号的四则运算的方式。

这里的困难在于乘除运算的优先级高于加减运算，并且加入了括号，使得问题变得更加困难。

20世纪50年代，波兰逻辑学家想到了**一种不需要括号的后缀表达法，我们也把它称为逆波兰表示**。

比如：`9+(3-1)*3+10/2`，如果用后缀表示法就是`9 3 1 - 3 * + 10 2 / +`,这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是要在运算数字的后面出现。

# 后缀表达式的计算方式 #

为了解释后缀表达式的好处，我们先来看看，计算机是如何计算后缀表达式的。

后缀表达式`9 3 1 - 3 * + 10 2 / +`

规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，然后计算结果进栈，一直到最终获得结果。

![图示][SouthEast]

![图示][SouthEast 1]

![图示][SouthEast 2]

![图示][SouthEast 3]

果然后缀表达式可以很顺利的解决计算问题。那么这个后缀表达式是怎么得出来的呢？

## 中缀表达式转后缀表达式 ##

我们把平时标准的四则运算表达式比如`9+(3-1)*3+10/2` 叫做中缀表达式。

中缀表达式：`9+(3-1)*3+10/2` 转换后缀表达式： `9 3 1 - 3 * + 10 2 / +`

规则：

1.  当当前字符为数字时，直接输出；
2.  当当前字符为”(“时，将其压栈；
3.  当当前字符为”)”时，则弹出堆栈中最上的”(“之前的所有运算符并输出，然后删除堆栈中的”(” ；
4.  当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到”(“之前为止)，输出，再将当前运算符压栈；
5.  最后弹出所有栈中的内容输出

![图示][SouthEast 4]

![图示][SouthEast 5]

![图示][SouthEast 6]

![图示][SouthEast 7]

![图示][SouthEast 8]

# 代码PHP #

以下代码为本人个人所写，存在诸多bug，意思点到为止，如有不到之处，敬请指出。

<?php
    //将数字项和符号项用空格分隔开
    function getItem($str)
    {
         
        $arr = [];
        $num = "";
        for ($i = 0; $i < strlen($str); $i++) {
            //如果是个数字，并且不为最后一项
            if (is_numeric($str[$i]) && $i != strlen($str) - 1) {
                $num .= $str[$i];
            } else {
                //如果不是个数字，并且num不为空，则放入数组中
                if (!empty($num)) {
                    $arr[] = $num;
                    $num = "";
                }
                //如果是符号，或者最后一项，直接放入数组中
                $arr[] = $str[$i];
            }
        }
        return implode(" ", $arr);
    }
    //将中缀表达式转换成后缀表达式
    function centerToEnd($str_center)
    {
         
        $stack = new \SplStack();
        $arr = explode(" ", $str_center);
        $arr1 = [];
        for ($i = 0; $i < count($arr); $i++) {
            if (is_numeric($arr[$i])) {
        //如果是个数字，直接放入数组，输出
                $arr1[]= $arr[$i];
            }else{
                if($arr[$i]=="("){
        //如果是左括号，则入栈
                    $stack->push($arr[$i]);
                }else if($arr[$i]==")"){
        //如果是右括号，则弹出堆栈中最上的"("之前的所有运算符并输出，然后删除堆栈中的"("
                    while(true){
                       $s = $stack->pop();
                       if($s=="("){
                           break;
                       }else{
                           $arr1[]=$s;
                       }
                   }
                }else if($arr[$i]=="+"||$arr[$i]=="-"){
        //当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到"("之前为止)，输出，再将当前运算符压栈
                    while($stack->count()>0){
                        $s = $stack->pop();
                        if($s=="("){
                            break;
                        }else{
                            $arr1[]=$s;
                        }
                    }
                } else if($arr[$i]=="*"||$arr[$i]=="/"){
        //当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到"("之前为止)，输出，再将当前运算符压栈
                    while($stack->count()>0){
                        $s = $stack->pop();
                        if($s=="("){
                            break;
                        }else if($s=="+"||$s=="-"){
                            $stack->push($s);
                            break;
                        }else{
                            $arr1[]=$s;
                        }
                    }
                }
                if($arr[$i]!==")"){
        //将当前运算符压入栈
                    $stack->push($arr[$i]);
                }
            }
        }
        //最后弹出栈中的全部内容
        while($stack->count()>0){
            $arr1[]=$stack->pop();
        }
        return implode(" ",$arr1);
    }
    //计算后缀式的和
    function sumEnd($str){
         
        $arr = explode(" ", $str);
        $stack = new \SplStack();
        for ($i = 0; $i < count($arr); $i++) {
            if (is_numeric($arr[$i])) {
        //如果是数字，直接压入栈中
                $stack->push($arr[$i]);
            } else {
        //如果是符号，则弹出栈顶的两个数，进行运算，然后将运算结果压入栈中
                $n2 = $stack->pop();
                $n1 = $stack->pop();
                $stack->push(eval("return " . $n1 . $arr[$i] . $n2 . ";"));
            }
        }
        return $stack->pop();//弹出最后结果
    }
    
    $str = "9+(3-1)*3+10/2";
    //$str = trim(fgets(STDIN));//标准输入
    $str_center = getItem($str);
    //echo $str_center;//9 + ( 3 - 1 ) * 3 + 10 / 2
    $str_end = centerToEnd($str_center);
    //echo $str_end;//9 3 1 - 3 * + 10 2 / +
    echo sumEnd($str_end);

[SouthEast]: /images/20220616/d7658ed67fbb481c928eacd9607854d4.png
[SouthEast 1]: /images/20220616/c92a6514aa0544a7a353e15b5d04a4fd.png
[SouthEast 2]: /images/20220616/69a4f7bd1c2442cfa44b82ac032b3286.png
[SouthEast 3]: /images/20220616/2ca384aab5a942b98c81c59f14fc6661.png
[SouthEast 4]: /images/20220616/94ed98f9d126443c8cca06da84d8ac14.png
[SouthEast 5]: /images/20220616/a94b08fcb36b4568bec84414bab1dbef.png
[SouthEast 6]: /images/20220616/099ccf9dbd8e41ccab602f93d7a3acc6.png
[SouthEast 7]: /images/20220616/4e34acc891ff4b53ad2d7fa2c7f3f324.png
[SouthEast 8]: /images/20220616/1d2bed702da940b08f59484c99dbdcdd.png