Clever Geek Handbook

Algoritmo para calcular una expresión aritmética como una cadena

Nuestra gloriosa empresa tiene un muy buen sistema de incentivos, así se llama. calificaciones: cada seis meses, cualquier desarrollador puede aumentar su calificación, lo que implica un aumento de salario. En otras palabras, una calificación es una certificación. ¿Quieres incrementar tu salario? Una vez cada seis meses, puede obtener la certificación para el siguiente paso y pasar de junior a senior (no puede saltar más de dos pasos a la vez). La certificación se lleva a cabo de manera amistosa, las preguntas se publican en la base de conocimientos, no hay trámites burocráticos. La condición para la admisión a la certificación es la solución de un problema algorítmico.







Entonces, estoy certificado y se me asigna una tarea: calcular una expresión aritmética en forma de cadena . Sí, una pregunta basura, dices (como hice yo al principio). Todo esto se ha descrito desde hace mucho tiempo, y aquí no hay nada complicado. Tendrás razón y estarás equivocado al mismo tiempo. La pregunta es, por supuesto, basura, pero esta es una tarea algorítmica . No puede usar bibliotecas listas para usar, necesita escribir una solución algorítmica. Y me sumergí en el mundo de los operandos, operadores, tanto binarios como unarios. Y cómo analizar todo esto maravillosamente, cómo no confundirse con los paréntesis, y ... lo más insidioso fue el menos unario.







Escribiremos la solución en php.







Por supuesto, no hay nada nuevo en este problema. Después de buscar en Google durante un tiempo, encontramos que para analizar una expresión aritmética como una cadena, por máquina, la notación polaca inversa es la más adecuada . Hay muchos materiales en el HMO, no tiene sentido desarmarlo en detalle. Por ejemplo, un enlace a una wiki .







Un ejemplo de una entrada en la HMO: 3 4 2 + *









De forma simplificada, podemos decir que el OPP es un registro de una expresión aritmética, en el que los operadores se escriben después de los operandos y en el que no hay paréntesis.

Por operandos nos referimos a números reales, por operadores - símbolos de operaciones aritméticas +, -, *, /, ^







¿Por qué HMO es tan bueno para la computación automática?







, , . . ( ).

, , , , , , , . , .







( ) :







<?php

$expression = explode(' ', '32 44 2 + *');

$stack = [];

foreach ($expression as $item) {
    if (is_numeric($item)) {
        $stack[] = (float)$item;
        continue;
    }
    $right = array_pop($stack);
    $left = array_pop($stack);
    switch ($item) {
        case '-':
            $stack[] = $left - $right;
            break;
        case '+':
            $stack[] = $left + $right;
            break;
        case '*':
            $stack[] = $left * $right;
            break;
        case '/':
            $stack[] = $left / $right;
            break;
        case '^':
            $stack[] = $left ** $right;
            break;
    }
}
//    
echo $stack[0] . PHP_EOL;


, , . :







,

.. -



() . , .

. , ~



.

— ( )!







? - ( ), ? , ?







, — , , , , .







. () :







  1. , , -.
  2. — .


? :

$a = -2





, ?

$a



2.

— . . 2, . .. 0.

.. $a



0 - 2



. , .







. , --2



.

? , : 0 - (0 - 2)



.

.. — , , .







, :







  • — -



    (), ,




  1. , ( )
  2. , , ( ~)




, . .







.







:







    private const UNARY_MINUS = '~';
    private const OPEN_BRACKET = '(';
    private const CLOSE_BRACKET = ')';
    private const MINUS = '-';
    private const PLUS = '+';
    private const DIVISION = '/';
    private const MULTIPLICATION = '*';
    private const EXPONENTIATION = '^';

    private const PRIORITY = [
        self::OPEN_BRACKET => 0,
        self::CLOSE_BRACKET => null,
        self::PLUS => 2,
        self::MINUS => 2,
        self::MULTIPLICATION => 3,
        self::DIVISION => 3,
        self::EXPONENTIATION => 4,
        self::UNARY_MINUS => 5
    ];


:







    private const RIGHT_ASSOCIATIVE_EXPRESSION = [
        self::EXPONENTIATION, self::UNARY_MINUS
    ];


( ) .









,













  • , —







  • , , ,















  • , , , , . , , — .

    .
  • , , , .
  • —


. .









"" 2 * (2 + -2 ^ 2 ^ 3) - 1



, 



















    $stack = [];
    $outString = [];


2 * (2 + -2 ^ 2 ^ 3) - 1









  • 2, — 







    $outString = [2];


  • — *



    — 







    $outString = [2];
$stack = ['*'];


  • — (



    — 







    $outString = [2];
$stack = ['*', '('];


  • — 2 — 







    $outString = [2, 2];
$stack = ['*', '('];


  • — +



    — 







    $outString = [2, 2];
$stack = ['*', '(', '+'];


  • — ~



    — 







    $outString = [2, 2];
$stack = ['*', '(', '+', '~'];


  • — 2 — 







    $outString = [2, 2, 2];
$stack = ['*', '(', '+', '~'];


  • — ^



    — , ^ 









    $outString = [2, 2, 2, '~'];
$stack = ['*', '(', '+', '^'];




… — , , , , , , . .

, , . .







2 2 2 ~ 2 3 ^ ^ + * 1 -









, , , .







  • .
  • , .
  • , , (0 ).








  • —
  • —
  • ,


Si la línea termina, devolvemos el valor calculado de la pila (si la expresión aritmética es correcta, entonces un elemento permanecerá en la pila).









Solución completa en idioma php









Revelación

Calculate







<?php
require_once __DIR__ . '/Calculate.php';

$expression = '2.5 * (-22 + 2 ^ 2 ^ 3) * (3 - 1)' . PHP_EOL;
$calc = new Calculate($expression);
if ($calc->postfixString) {
    echo ' : ' . $expression;
    echo '    (~ -   ): ' . $calc->postfixString . PHP_EOL;
    echo '   : ' . $calc->result . PHP_EOL;
} else {
    echo $calc->result . PHP_EOL;
}


Calculate







<?php

/** @noinspection PhpIllegalPsrClassPathInspection */

class Calculate
{
    private const UNARY_MINUS = '~';
    private const OPEN_BRACKET = '(';
    private const CLOSE_BRACKET = ')';
    private const MINUS = '-';
    private const PLUS = '+';
    private const DIVISION = '/';
    private const MULTIPLICATION = '*';
    private const EXPONENTIATION = '^';

    private const PRIORITY = [
        self::OPEN_BRACKET => 0,
        self::CLOSE_BRACKET => 1,
        self::PLUS => 2,
        self::MINUS => 2,
        self::MULTIPLICATION => 3,
        self::DIVISION => 3,
        self::EXPONENTIATION => 4,
        self::UNARY_MINUS => 5
    ];

    private const RIGHT_ASSOCIATIVE_EXPRESSION = [
        self::EXPONENTIATION, self::UNARY_MINUS
    ];

    private array $stack = [];
    private array $outString = [];

    /**
     * @var float|string
     */
    public $result;
    public string $postfixString = '';

    public function __construct(string $expression)
    {
        try {
            $expression = $this->checkExpression($expression);
            $this->createOutString($expression);
            $this->postfixString = implode(' ', $this->outString);
            $this->calcFromOutString();
        } catch (Exception $e) {
            $this->result = $e->getMessage();
        }
    }

    private function checkExpression(string $expression): string
    {
        preg_match('/-?\d+\s+-?\d+/', $expression, $matches);
        if ($matches) {
            throw new DomainException('   !');
        }
        $openBracket = substr_count($expression, self::OPEN_BRACKET);
        $closeBracket = substr_count($expression, self::CLOSE_BRACKET);
        if ($openBracket !== $closeBracket) {
            throw new DomainException(' !');
        }
        //     
        $expression = preg_replace('/\s/', '', $expression);
        $expression = str_replace(',', '.', $expression);
        preg_match('/[^\d()+\/*-.^]+/', $expression, $matches);
        if ($matches) {
            throw new DomainException('!      , ,   +, -, *, /, ^');
        }

        return $expression;
    }

    private function calc($left, $right, $operator)
    {
        switch ($operator) {
            case self::MINUS:
                return $left - $right;
            case self::PLUS:
                return $left + $right;
            case self::MULTIPLICATION:
                return $left * $right;
            case self::EXPONENTIATION:
                return $left ** $right;
            case self::DIVISION:
                if ($right == 0) {
                    throw new DomainException('  !');
                }
                return $left / $right;
            default:
                throw new DomainException('  ' . $operator);
        }
    }

    /**
     *    
     */
    private function createOutString(string $expression)
    {
        $length = strlen($expression) - 1;
        $number = null;

        for ($i = 0; $i <= $length; $i++) {
            $item = $expression[$i];
            $left = $i === 0 ? null : $expression[$i - 1];
            $right = $i === $length ? null : $expression[$i + 1];

            if (is_numeric($item) || $item === '.') {
                if ($item === '.') {
                    if ($left === null || $right === null || !is_numeric($left) || !is_numeric($right)) {
                        throw new DomainException('  !');
                    }
                }
                $number .= $item;
                if ($right !== '.' && !is_numeric($right)) {
                    $this->outString[] = (float)$number;
                    $number = null;
                }
                continue;
            }

            if ($item === self::MINUS) {
                if (!is_numeric($left) && $left !== self::CLOSE_BRACKET) {
                    $item = self::UNARY_MINUS;
                }
            }

            if ($item === self::OPEN_BRACKET && is_numeric($left)) {
                throw new DomainException('    ');
            }
            if ($item === self::CLOSE_BRACKET && (is_numeric($right) || $right === self::OPEN_BRACKET)) {
                throw new DomainException('    ');
            }

            $this->addToStackAndPushFromStack($item);
        }

        while ($this->stack) {
            $this->outString[] = array_pop($this->stack);
        }
    }

    private function addToStackAndPushFromStack(string $operator)
    {
        if (!$this->stack || $operator === self::OPEN_BRACKET) {
            $this->stack[] = $operator;
            return;
        }

        $stack = array_reverse($this->stack);

        if ($operator === self::CLOSE_BRACKET) {
            foreach ($stack as $key => $item) {
                unset($stack[$key]);
                if ($item === self::OPEN_BRACKET) {
                    $this->stack = array_reverse($stack);
                    return;
                }
                $this->outString[] = $item;
            }
        }

        foreach ($stack as $key => $item) {
            if (in_array($item, self::RIGHT_ASSOCIATIVE_EXPRESSION) && $item === $operator) {
                break;
            }
            if (self::PRIORITY[$item] < self::PRIORITY[$operator]) {
                break;
            }
            $this->outString[] = $item;
            unset($stack[$key]);
        }

        $this->stack = array_reverse($stack);
        $this->stack[] = $operator;
    }

    /**
     *    
     */
    private function calcFromOutString()
    {
        $stack = [];
        foreach ($this->outString as $item) {
            if (is_float($item)) {
                $stack[] = $item;
                continue;
            }
            if ($item === self::UNARY_MINUS) {
                $last = array_pop($stack);
                if (!is_numeric($last)) {
                    throw new DomainException(' !');
                }
                $stack[] = 0 - $last;
                continue;
            }
            $right = array_pop($stack) ?? null;
            $left = array_pop($stack) ?? null;
            if ($right === null || $left === null) {
                throw new DomainException(' !');
            }
            $stack[] = $this->calc($left, $right, $item);
        }
        $this->result = $stack[0];
    }
}


Resumamos



Para un hermoso cálculo de una expresión aritmética en forma de cadena, necesita:







  1. Comprender qué es la notación polaca inversa y por qué es ideal para la computación automática.
  2. Convierta una expresión aritmética en un HMO y calcule


Tanto para el primer como para el segundo punto, el concepto clave es la pila, una secuencia organizada según el principio, el último en entrar, el primero en salir. El último elemento de la pila siempre está encima de la pila.







More articles:


All Articles