LEN

收藏 PHP 计算器
从网上找的韩顺平老师算法讲解的 使用堆栈 实现计算器<?php /** * Created by PhpS...
扫描右侧二维码阅读全文
23
2019/04

收藏 PHP 计算器

从网上找的韩顺平老师算法讲解的 使用堆栈 实现计算器

<?php
/**
 * Created by PhpStorm.
 * User: Len
 * Date: 2019/4/20
 * Time: 18:35
 * Desc: 使用堆栈实现一个计算器 仅支持 加减乘除
 */

namespace Library;


use Helper\Common;

class StackCalculateor
{
    // 默认是-1,表示该栈是空的
    public $top = -1;

    // $maxSize表示栈最大容量
    public $maxSize = 15;

    public $stack = array();

    /**
     * @des 运算
     * @param $str
     * @return bool|float|int
     * ------------------------------------------------------------
     */
    public static function run($str)
    {
        $numsStack = new self();
        $operStack = new self();

        // 字符串的指针
        $index = 0;

        // 声明一个用于组合联系数字的变量
        $keepNum = '';

        if (!mb_strlen($str)) return false;

        while (true) {
            $val = mb_substr($str, $index, 1);

            //如果是一个符号就入符号栈 否则入数栈
            if ($operStack->isOper($val) == true) {
                //符号入栈前需要判断一下 栈为空直接入栈 不为空需要比较当前运算符与栈顶端的运算符
                //如果当前运算符的优先级低于栈内的 则需要运算
                if ($operStack->isEmpty()) {
                    $operStack->push($val);
                } else {
                    while (!$operStack->isEmpty() && $operStack->PRI($val) <= $operStack->PRI($operStack->getTop())) {
                        //当前符号的优先级要直到高于栈内的时候才能入栈 否则要计算
                        //当前运算符的优先级低于栈内的 则运算
                        $num1 = $numsStack->pop();
                        $num2 = $numsStack->pop();
                        $oper = $operStack->pop();
                        $res = $numsStack->getResult($num1, $num2, $oper);
                        //计算完毕将结果入栈
                        $numsStack->push($res);
                    }
                    //把当前这个符号再入符号栈
                    $operStack->push($val);
                }

            } else {
                //考虑如果是连续数字的问题
                $keepNum .= $val;
                //先判断是否已经到字符串最后.如果已经到最后,就直接入栈.
                if ($index == mb_strlen($str) - 1) {
                    $numsStack->push($keepNum);//是数字直接入栈
                } else {
                    //要判断一下$ch字符的下一个字符是数字还是符号.
                    if ($operStack->isOper(mb_substr($str, $index + 1, 1))) {
                        $numsStack->push($keepNum);
                        $keepNum = '';
                    }
                }
            }

            $index++;//让$index指向下一个字符.

            if ($index == mb_strlen($str)) break;//已扫描到字符串的末尾 就退出while循环
        }

        /*
         4. 当扫描完毕后,就依次弹出数栈和符号栈的数据,并计算,最终留在数栈的值,就是运算结果,只有符号栈不空就一直计算
        */
        while (!$operStack->isEmpty()) {
            $num1 = $numsStack->pop();
            $num2 = $numsStack->pop();
            $oper = $operStack->pop();
            $res = $numsStack->getResult($num1, $num2, $oper);
            //计算完毕将结果入栈
            $numsStack->push($res);
        }

        return $res;
    }

    /**
     * @des 判断是否是一个运算符
     * @param $val
     * @return bool
     * ------------------------------------------------------------
     */
    public function isOper($val)
    {
        if ($val == '+' || $val == '-' || $val == '*' || $val == '/') return true;
    }

    /**
     * @des 判断栈是否为空
     * @return bool
     * ------------------------------------------------------------
     */
    public function isEmpty()
    {
        if ($this->top == -1) return true;
    }

    /**
     * @des 入栈
     * @param $val
     * ------------------------------------------------------------
     */
    public function push($val)
    {
        //先判断栈是否已经满了
        if ($this->top == $this->maxSize - 1) return;

        $this->top++;

        $this->stack[$this->top] = $val;
    }

    /**
     * 比较运算符的优先级
     * 我把 * 和/运算符的优先级看作1
     * +和- 看作0
     * 通过它们之间的比较就能得出它们的优先级谁更高
     * @param $oper
     * @return int
     * ------------------------------------------------------------
     */
    public function pri($oper)
    {
        if ($oper == '*' || $oper == '/')
            return 1;
        else if ($oper == '+' || $oper == '-')
            return 0;
    }

    /**
     * @des 返回栈顶端的值
     * @return mixed
     * ------------------------------------------------------------
     */
    public function getTop()
    {
        return $this->stack[$this->top];
    }

    /**
     * @des 出栈
     * @return null|number
     * ------------------------------------------------------------
     */
    public function pop()
    {
        //判断是否栈空
        if ($this->top == -1)
            return null;

        //把栈顶的值,取出
        $topVal = $this->stack[$this->top];

        $this->top--;

        return $topVal;

    }

    /**
     * @des 运算
     * @param $num1
     * @param $num2
     * @param $oper
     * @return float|int
     * ------------------------------------------------------------
     */
    public function getResult($num1, $num2, $oper)
    {
        switch ($oper) {
            case '+':
                $res = Common::sbcadd($num2, $num1);
                break;
            case '-':
                $res = Common::sbcsub($num2, $num1);
                break;
            case '*':
                $res = Common::sbcmul($num2, $num1);
                break;
            case '/':
                $res = Common::sbcdiv($num2, $num1);
                break;
        }

        return $res;
    }

    /**
     * 显示栈的所有数据的方法
     * ------------------------------------------------------------
     */
    public function showStack()
    {
        if ($this->top == -1) return;

        echo '当前栈的情况是....', PHP_EOL;

        for ($i = $this->top; $i > -1; $i--) {
            echo ' stack[' . $i . ']=' . $this->stack[$i], PHP_EOL;
        }
    }

}
Last modification:April 23rd, 2019 at 10:36 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment Cancel reply

6 comments

  1. 一冉再

    ```
    class StrToValue
    {
    private static $operatorLevel = [
    '**' => 0,
    '++' => 1,
    '--' => 1,
    '~' => 1,
    '*' => 2,
    '/' => 2,
    '%' => 2,
    '+' => 3,
    '-' => 3,
    '>' => 4,
    '&' => 5,
    '^' => 6,
    '|' => 7,
    '=' => 8,
    '+=' => 8,
    '-=' => 8,
    '*=' => 8,
    '**=' => 8,
    '/=' => 8,
    '.=' => 8,
    '%=' => 8,
    '&=' => 8,
    '|=' => 8,
    '^=' => 8,
    '>=' => 8,
    ];
    private static $full = [
    '~',
    '*',
    '/',
    '%',
    '+',
    '-',
    ];
    private static $nums = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
    /**
    * @param $str
    * @return array
    * @throws Exception
    */
    public static function test($str)
    {
    $len = strlen($str);
    $numStack = $operatorStack = [];
    $num = 0;
    $operator = '';
    $isNum = $isOperator = false;
    $operators = array_keys(self::$operatorLevel);
    for ($i = 0; $i < $len; $i++) {
    if ($str[$i] === ' ') {
    continue;
    }
    if (in_array($str[$i], self::$nums, true)) {
    if ($isNum) {
    $num .= $str[$i];
    } else {
    $num = $str[$i];
    if (count($operatorStack) > 0) {
    $op = array_pop($operatorStack);
    if (self::$operatorLevel[$op] > self::$operatorLevel[$operator]) {
    $operatorStack[] = $op;
    $operatorStack[] = $operator;
    } else if (count($numStack) > 0) {
    $right = array_pop($numStack);
    $left = array_pop($numStack);
    $aaa = 'return ' . ($left ?? '') . $op . $right . ';';
    $numStack[] = eval($aaa);
    $operatorStack[] = $operator;
    }
    } else if ($isOperator !== false) {
    $operatorStack[] = $operator;
    }
    }
    $isNum = true;
    $isOperator = false;
    } else if (in_array($str[$i], $operators, true)) {
    if ($isOperator) {
    $operator .= $str[$i];
    } else {
    $operator = $str[$i];
    if ($isNum === false) {
    $numStack[] = !in_array($operator, self::$full, true) ? '' : 0;
    } else {
    $numStack[] = $num;
    }
    }
    $isNum = false;
    $isOperator = true;
    } else {
    throw new Exception($str . '包含无效的字符' . $str[$i]);
    }
    }
    if ($isNum) {
    $numStack[] = $num;
    }
    if ($isOperator) {
    $operatorStack[] = $operator;
    }
    while (!empty($operatorStack)) {
    $right = array_pop($numStack);
    $left = array_pop($numStack);
    $op = array_pop($operatorStack);
    $numStack[] = eval('return ' . $left . $op . $right . ';');
    }
    return $numStack[0];
    }
    }
    ```

    1. LEN
      @一冉再

      ` eval('return ' . $left . $op . $right . ';');`
      这个函数生产环境是禁用的

      1. 一冉再
        @LEN

        为什么呢?愿听老哥指教

        1. LEN
          @一冉再

          eval 里面有外来参数如果不处理过滤就会` web shell `
          线上生产环境一般都是禁用该函数的

  2. 211212

    学习学习|´・ω・)ノ

  3. 薛定谔的电炒勺

    学习学习