Clever Geek Handbook

Algorithm for calculating an arithmetic expression as a string

Our glorious company has a very good incentive system, so-called. grades: every six months, any developer can increase their grade, which entails an increase in salary. In other words, a grade is an attestation. Do you want to increase your salary? Once every six months, you can be certified for the next step, and grow from junior to senior (you can jump no more than two steps at a time). Attestation takes place in a friendly manner, questions are posted in the knowledge base, there is no bureaucratic red tape. The condition for admission to certification is the solution of an algorithmic problem.







And so I am certified, and I am given a task: to calculate an arithmetic expression in the form of a string . Yes, bullshit is a question, you say (as I did at the beginning). All this has long been described, and there is nothing complicated here. You will be right and wrong at the same time. The question is, of course, garbage, but this is an algorithmic task. You cannot use ready-made libraries, you need to write an algorithmic solution. And I plunged into the world of operands, operators, both binary and unary. And how to parse all this beautifully, how not to get confused with parentheses, and ... the unary minus turned out to be the most insidious.







We will write the solution in php.







There is, of course, nothing new in this problem. After googling for a while, we find that for parsing an arithmetic expression as a string, by machine, the Reverse Polish notation is best suited . There are a lot of materials on the HMO, it makes no sense to disassemble it in detail. For example, a link to a wiki .







An example of an entry in the HMO: 3 4 2 + *









In a simplified form, we can say that the OPP is a record of an arithmetic expression, in which operators are written after the operands, and in which there are no parentheses.

By operands we mean real numbers, by operators - symbols of arithmetic operations +, -, *, /, ^







Why is HMO so good for 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 ).








  • —
  • —
  • ,


If the line ends, we return the calculated value from the stack (if the arithmetic expression is correct, then one element will remain on the stack).









Complete solution in language 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];
    }
}


Let's summarize



For a beautiful calculation of an arithmetic expression in the form of a string, you need:







  1. Understand what Reverse Polish notation is, and why it is ideal for machine computing
  2. Convert an arithmetic expression to an HMO, and calculate it


For both the first and second points, the key concept is a stack - a sequence organized according to the principle - the last one in, the first one out. The last element of the stack is always at the top of the stack.







More articles:


All Articles