私たちの栄光ある会社には、いわゆる非常に優れたインセンティブシステムがあります。成績：6か月ごとに、すべての開発者が成績を上げることができます。これには、給与の引き上げが伴います。言い換えれば、成績は証明です。給料を上げたいですか？6か月に1回、次のステップの認定を受け、ジュニアからシニアに成長できます（一度にジャンプできるのは2ステップまでです）。証明は友好的な方法で行われ、質問はナレッジベースに投稿され、官僚的な官僚的な形式主義はありません。認定への入学の条件は、アルゴリズムの問題の解決です。
そして、私は認定され、文字列の形式で算術式を計算するというタスクが与えられます。はい、ごみの質問です、あなたは言います（私が最初にしたように）。これはすべて長い間説明されており、ここでは複雑なことは何もありません。あなたは同時に正しいことと間違っていることになるでしょう。もちろん、問題はゴミですが、これはアルゴリズムのタスクです。既製のライブラリを使用することはできません。アルゴリズムソリューションを作成する必要があります。そして、バイナリと単項の両方のオペランド、演算子の世界に飛び込みました。そして、これらすべてを美しく解析する方法、括弧と混同しないようにする方法、そして...最も陰湿なのは単項マイナスでした。
ソリューションをphpで記述します。
もちろん、この問題に新しいことは何もありません。しばらくグーグルした後、算術式を文字列として解析するには、機械で逆ポーランド記法が最適であることがわかりました。HMOには多くの資料があり、詳細に分解しても意味がありません。たとえば、ウィキへのリンク。
HMOのエントリの例： 3 4 2 + *
簡略化すると、OPPは、オペランドの後に演算子が記述され、括弧がない算術式のレコードであると言えます。
オペランドとは実数を意味し、演算子とは算術演算の記号+、-、*、/、^
HMOがマシンコンピューティングに非常に適しているのはなぜですか？
, , . . ( ).
, , , , , , , . , .
( ) :
<?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 ).
- —
- —
- ,
行が終了すると、スタックから計算値が返されます（算術式が正しければ、1つの要素がスタックに残ります）。
言語による完全なソリューション 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];
}
}
まとめましょう
文字列形式の算術式を美しく計算するには、次のものが必要です。
- 逆ポーランド記法とは何か、そしてそれがマシンコンピューティングに理想的である理由を理解する
- 算術式をHMOに変換し、計算します
最初のポイントと2番目のポイントの両方で、重要な概念はスタック（原則に従って編成されたシーケンス）です。最後の1つが入り、最初の1つが出ます。スタックの最後の要素は常にスタックの一番上にあります。