Notre glorieuse entreprise a un très bon système d'incitation, soi-disant. grades: tous les six mois, tout développeur peut augmenter son grade, ce qui entraîne une augmentation de salaire. En d'autres termes, une note est une attestation. Voulez-vous augmenter votre salaire? Une fois tous les six mois, vous pouvez être certifié pour l'étape suivante et passer de junior à senior (vous ne pouvez pas sauter plus de deux étapes à la fois). L'attestation se déroule de manière amicale, les questions sont affichées dans la base de connaissances, il n'y a pas de paperasse bureaucratique. La condition d'admission à la certification est la solution d'un problème algorithmique.
Et donc je suis certifié, et on me donne une tâche: calculer une expression arithmétique sous la forme d'une chaîne . Oui, une question poubelle, dites-vous (comme je l'ai fait au début). Tout cela a longtemps été décrit, et il n'y a rien de compliqué ici. Vous aurez raison et tort en même temps. La question est, bien sûr, des déchets, mais c'est une tâche algorithmique . Vous ne pouvez pas utiliser de bibliothèques prêtes à l'emploi, vous devez écrire une solution algorithmique. Et je me suis plongé dans le monde des opérandes, des opérateurs, à la fois binaires et unaires. Et comment analyser tout cela magnifiquement, comment ne pas se confondre avec les parenthèses, et ... le plus insidieux était le moins unaire.
Nous Ă©crirons la solution en php.
Il n'y a, bien sûr, rien de nouveau dans ce problème. Après avoir cherché sur Google pendant un certain temps, nous constatons que pour analyser une expression arithmétique sous forme de chaîne, par machine, la notation polonaise inversée est la mieux adaptée . Il y a beaucoup de matériaux sur le HMO, cela n'a aucun sens de le démonter en détail. Par exemple, un lien vers un wiki .
Un exemple d'entrée dans le HMO: 3 4 2 + *
Dans une forme simplifiée, nous pouvons dire que l'OPP est un enregistrement d'une expression arithmétique, dans laquelle les opérateurs sont écrits après les opérandes, et dans lequel il n'y a pas de parenthèses.
Par opérandes, nous entendons des nombres réels, par opérateurs - symboles d'opérations arithmétiques +, -, *, /, ^
Pourquoi HMO est-il si bon pour l'informatique machine?
, , . . ( ).
, , , , , , , . , .
( ) :
<?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;
, , . :
,
.. -
() . , .
. , ~
.
— ( )!
? - ( ), ? , ?
, — , , , , .
. () :
- , , -.
- — .
? :
$a = -2
, ?
$a
2.
— . . 2, . .. 0.
.. $a
0 - 2
. , .
. , --2
.
? , : 0 - (0 - 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 ligne se termine, nous renvoyons la valeur calculée à partir de la pile (si l'expression arithmétique est correcte, alors un élément restera sur la pile).
Solution complète en langue php
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];
}
}
RĂ©sumons
Pour un beau calcul d'une expression arithmétique sous forme de chaîne, il vous faut:
- Comprendre ce qu'est la notation polonaise inversée et pourquoi elle est idéale pour l'informatique machine
- Convertissez une expression arithmétique en HMO et calculez-la
Pour les premier et deuxième points, le concept clé est la pile - une séquence organisée selon le principe - le dernier entré, le premier sorti. Le dernier élément de la pile est toujours au-dessus de la pile.