Clever Geek Handbook

Algorithmus zur Berechnung eines arithmetischen Ausdrucks als Zeichenfolge

Unser ruhmreiches Unternehmen hat ein sehr gutes Anreizsystem, das sogenannte. Noten: Alle sechs Monate kann jeder Entwickler seine Note erhöhen, was eine Gehaltserhöhung zur Folge hat. Mit anderen Worten, eine Note ist eine Bescheinigung. Möchten Sie Ihr Gehalt erhöhen? Einmal alle sechs Monate können Sie fĂŒr den nĂ€chsten Schritt zertifiziert werden und von Junior zu Senior wachsen (Sie können nicht mehr als zwei Schritte gleichzeitig springen). Die Bescheinigung erfolgt auf freundliche Weise, Fragen werden in der Wissensdatenbank veröffentlicht, es gibt keine bĂŒrokratische BĂŒrokratie. Voraussetzung fĂŒr die Zulassung zur Zertifizierung ist die Lösung eines algorithmischen Problems.







Und so bin ich zertifiziert und habe die Aufgabe, einen arithmetischen Ausdruck in Form einer Zeichenkette zu berechnen . Ja, eine MĂŒllfrage, sagst du (wie ich es am Anfang getan habe). All dies wurde lange beschrieben, und hier gibt es nichts Kompliziertes. Sie werden gleichzeitig richtig und falsch sein. Die Frage ist natĂŒrlich MĂŒll, aber dies ist eine algorithmische Aufgabe. Sie können keine vorgefertigten Bibliotheken verwenden, sondern mĂŒssen eine algorithmische Lösung schreiben. Und ich stĂŒrzte mich in die Welt der Operanden, Operatoren, sowohl binĂ€r als auch unĂ€r. Und wie man das alles wunderschön analysiert, wie man nicht mit Klammern verwechselt wird und ... das heimtĂŒckischste war das unĂ€re Minus.







Wir werden die Lösung in PHP schreiben.







An diesem Problem ist natĂŒrlich nichts Neues. Nachdem wir eine Weile gegoogelt haben, stellen wir fest, dass die umgekehrte polnische Notation am besten geeignet ist , um einen arithmetischen Ausdruck als Zeichenfolge maschinell zu analysieren . Es gibt viele Materialien auf dem HMO, es macht keinen Sinn, es im Detail zu zerlegen. Zum Beispiel ein Link zu einem Wiki .







Ein Beispiel fĂŒr einen Eintrag in der HMO: 3 4 2 + *









In vereinfachter Form können wir sagen, dass das OPP eine Aufzeichnung eines arithmetischen Ausdrucks ist, in dem Operatoren nach den Operanden geschrieben werden und in dem keine Klammern stehen.

Mit Operanden meinen wir reelle Zahlen, mit Operatoren - Symbole fĂŒr arithmetische Operationen +, -, *, /, ^







Warum ist HMO so gut fĂŒr Machine Computing?







, , . . ( ).

, , , , , , , . , .







( ) :







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








  • —
  • —
  • ,


Wenn die Zeile endet, geben wir den berechneten Wert vom Stapel zurĂŒck (wenn der arithmetische Ausdruck korrekt ist, bleibt ein Element auf dem Stapel).









Komplettlösung in Sprache 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];
    }
}


Fassen wir zusammen



FĂŒr eine schöne Berechnung eines arithmetischen Ausdrucks in Form einer Zeichenfolge benötigen Sie:







  1. Verstehen Sie, was Reverse Polish Notation ist und warum es ideal fĂŒr Machine Computing ist
  2. Konvertieren Sie einen arithmetischen Ausdruck in ein HMO und berechnen Sie ihn


Sowohl fĂŒr den ersten als auch fĂŒr den zweiten Punkt ist das SchlĂŒsselkonzept der Stapel - eine nach dem Prinzip organisierte Sequenz - der letzte Eingang, der erste Ausgang. Das letzte Element des Stapels befindet sich immer oben auf dem Stapel.







More articles:


All Articles