Clever Geek Handbook

Algoritma untuk menghitung ekspresi aritmatika sebagai string

Perusahaan kita yang gemilang memiliki sistem insentif yang sangat bagus, yang disebut demikian. nilai: setiap enam bulan, setiap pengembang dapat meningkatkan nilai mereka, yang memerlukan peningkatan gaji. Dengan kata lain, nilai adalah pengesahan. Apakah Anda ingin menaikkan gaji Anda? Setiap enam bulan sekali, Anda dapat disertifikasi untuk langkah berikutnya, dan berkembang dari junior ke senior (Anda tidak dapat melompat tidak lebih dari dua langkah sekaligus). Pengesahan berlangsung dengan ramah, pertanyaan diposting di basis pengetahuan, tidak ada birokrasi birokrasi. Syarat untuk masuk ke sertifikasi adalah solusi dari masalah algoritmik.







Jadi saya bersertifikat, dan saya diberi tugas: menghitung ekspresi aritmatika dalam bentuk string . Ya, pertanyaan sampah, kata Anda (seperti yang saya lakukan di awal). Semua ini telah lama dijelaskan, dan tidak ada yang rumit di sini. Anda akan benar dan salah pada saat bersamaan. Pertanyaannya adalah, tentu saja, sampah, tetapi ini adalah tugas algoritmik . Anda tidak dapat menggunakan pustaka yang sudah jadi, Anda perlu menulis solusi algoritmik. Dan saya terjun ke dunia operan, operator, baik biner maupun unary. Dan bagaimana mengurai semua ini dengan indah, bagaimana tidak bingung dengan tanda kurung, dan ... yang paling berbahaya adalah minus unary.







Kami akan menulis solusinya di php.







Tentu saja, tidak ada yang baru dalam masalah ini. Setelah googling beberapa saat, kami menemukan bahwa untuk mengurai ekspresi aritmatika sebagai string, dengan mesin, notasi Polandia Terbalik paling cocok . Ada banyak materi di HMO, tidak masuk akal untuk membongkarnya secara mendetail. Misalnya, tautan ke wiki .







Contoh entri di HMO: 3 4 2 + *









Dalam bentuk yang disederhanakan, kita dapat mengatakan bahwa OPP adalah catatan dari ekspresi aritmatika, di mana operator dituliskan setelah operan, dan tidak ada tanda kurung.

Yang kami maksud dengan operan adalah bilangan real, dengan operator - simbol operasi aritmatika +, -, *, /, ^







Mengapa HMO sangat bagus untuk komputasi mesin?







, , . . ( ).

, , , , , , , . , .







( ) :







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








  • —
  • —
  • ,


Jika garis berakhir, kami mengembalikan nilai yang dihitung dari tumpukan (jika ekspresi aritmatika benar, maka satu elemen akan tetap ada di tumpukan).









Solusi lengkap dalam bahasa 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];
    }
}


Mari kita rangkum



Untuk kalkulasi indah dari ekspresi aritmatika dalam bentuk string, Anda memerlukan:







  1. Pahami apa itu notasi Polandia Terbalik, dan mengapa itu ideal untuk komputasi mesin
  2. Ubah ekspresi aritmatika menjadi HMO, dan hitung


Untuk poin pertama dan kedua, konsep utamanya adalah tumpukan - urutan yang diatur menurut prinsip - yang terakhir masuk, keluar pertama. Elemen terakhir dari tumpukan selalu di atas tumpukan.







More articles:


All Articles