Clever Geek Handbook

Algoritmo para calcular uma expressão aritmética como uma string

Nossa gloriosa empresa tem um sistema de incentivos muito bom, assim chamado. notas: a cada seis meses, qualquer desenvolvedor pode aumentar sua nota, o que acarreta aumento de salário. Em outras palavras, uma nota é um atestado. Você quer aumentar seu salário? Uma vez a cada seis meses, você pode ser certificado para a próxima etapa e passar do júnior ao sênior (você não pode pular mais do que duas etapas por vez). A comprovação é feita de forma amigável, as dúvidas são postadas na base de conhecimento, não há burocracia. A condição de admissão à certificação é a solução de um problema algorítmico.







Portanto, estou certificado e recebo uma tarefa: calcular uma expressão aritmética na forma de uma string . Sim, uma pergunta sem sentido, você diz (como eu fiz no início). Tudo isso foi descrito há muito tempo e não há nada de complicado aqui. Você estará certo e errado ao mesmo tempo. A questão é, obviamente, lixo, mas esta é uma tarefa algorítmica . Você não pode usar bibliotecas prontas, você precisa escrever uma solução algorítmica. E eu mergulhei no mundo dos operandos, operadores, binários e unários. E como analisar tudo isso lindamente, como não se confundir com parênteses, e ... o mais insidioso era o menos unário.







Vamos escrever a solução em php.







É claro que não há nada de novo nesse problema. Depois de pesquisar um pouco no Google, descobrimos que, para analisar uma expressão aritmética como uma string, por máquina, a notação polonesa reversa é a mais adequada . Existem muitos materiais no HMO, não faz sentido desmontá-lo em detalhes. Por exemplo, um link para um wiki .







Um exemplo de entrada no HMO: 3 4 2 + *









De forma simplificada, podemos dizer que o OPP é um registro de uma expressão aritmética, na qual os operadores são escritos após os operandos, e na qual não existem parênteses.

Por operandos queremos dizer números reais, por operadores - símbolos de operações aritméticas +, -, *, /, ^







Por que o HMO é tão bom para computação de máquina?







, , . . ( ).

, , , , , , , . , .







( ) :







<?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 ).








  • —
  • —
  • ,


Se a linha terminar, retornamos o valor calculado da pilha (se a expressão aritmética estiver correta, um elemento permanecerá na pilha).









Solução completa no idioma php









Spoiler

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];
    }
}


Vamos resumir



Para um belo cálculo de uma expressão aritmética na forma de uma string, você precisa:







  1. Entenda o que é a notação polonesa reversa e por que ela é ideal para computação de máquina
  2. Converta uma expressão aritmética em um HMO e calcule-a


Tanto para o primeiro quanto para o segundo ponto, o conceito-chave é a pilha - uma sequência organizada de acordo com o princípio - o último a entrar, o primeiro a sair. O último elemento da pilha está sempre no topo da pilha.







More articles:


All Articles