欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-28 17:10:52
...

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

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

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

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

后缀表达式的计算方式

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

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

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

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

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

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

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

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

中缀表达式转后缀表达式

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

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

规则:

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

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

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

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

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

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

代码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);