Обратная польская запись: примеры реализации

Материал из Викиверситета
Перейти к навигации Перейти к поиску

Примеры реализации[править]

C++[править]

//Стандарт языка C++17
//Пример ввода: 8 9 + 1 7 - *

//______Реализация______

#include <iostream>
#include <string>
#include <functional>
#include <vector>
#include <map>
#include <cctype>

using namespace std;

int main()
{
    map<char, function<int64_t(const int64_t&, const int64_t&)>> operations;
    operations['+'] = [](const int64_t& a, const int64_t& b) constexpr { return a + b; };
    operations['-'] = [](const int64_t& a, const int64_t& b) constexpr { return a - b; };
    operations['*'] = [](const int64_t& a, const int64_t& b) constexpr { return a * b; };
    operations['/'] = [](const int64_t& a, const int64_t& b) constexpr { return a / b; };

    string expression;
    vector<int64_t> stack_;
    int64_t number = 0;
    bool flag = true;

    getline(cin, expression);

    for (const auto& i : expression)
    {
        if (isdigit(i))
        {
            number *= 10;
            number += (i - '0');
            flag = true;
        }
        else
        {
            if (i != ' ')
            {
                int64_t num2 = stack_.back();
                stack_.pop_back();
                int64_t num1 = stack_.back();
                stack_.pop_back();

                stack_.push_back(operations[i](num1, num2));
                flag = false;
            }
            else if (i == ' ' && flag)
            {
                stack_.push_back(number);
                number = 0;
            }
        }
    }

    cout << stack_.back();

    return 0;
}

Forth[править]

3 2 1 + *

Haskell[править]

calc :: String -> [Float]
calc = foldl f [] . words
  where 
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f xs y         = read y : xs

Erlang[править]

-module(calc).
-export([expr/1]).
expr(L) ->
    [Result] = lists:foldl(fun expr/2, [], string:tokens(L, " ")),
    Result.

expr("+", [A, B | T]) -> [A + B | T];
expr("-", [A, B | T]) -> [A - B | T];
expr("*", [A, B | T]) -> [A * B | T];
expr("/", [A, B | T]) -> [A / B | T];
expr(N, T) -> [read(N) | T].

read(N) ->
    case string:to_float(N) of
	{error, no_float} -> list_to_integer(N);
	{F, _} -> F
    end.

C[править]

/* Компиляция:
 *   gcc -o rpn rpn.c
 *
 * Использование:
 *   ./rpn <выражение>
 * 
 * Пример:
 *   ./rpn 3 5 +
 *
 * Замечание: знак умножения `*' заменен на `x', т.к. символ `*' используется
 * командной оболочкой.
 **/

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

#define STKDPTH 32 /* Глубина стека */

/* Значения, возвращаемые функцией parse */
#define VAL  0  /* В стек занесено новое значение */
#define ADD  1  /* Сложение */
#define SUB  2  /* Вычитание */
#define MUL  3  /* Умножение */
#define DIV  4  /* Деление */
#define SOF -1  /* Переполнение стека */
#define SUF -2  /* В стеке недостаточно операндов */
#define UNK -3  /* Неопознанное значение */

/* Глобальные переменные */
int scount;
double stack[STKDPTH];

/* Функция распознавания аргументов */
int parse(char *);

/* Точка входа */
int main(int argc, char **argv)
{
    /* Организуем цикл для перебора аргументов командной строки */
    while (*++argv) {

        /* Пытаемся распознать текущий аргумент как число или
         * символ арифметической операции */
        switch (parse(*argv)) {
            case VAL: continue;

            /* Вычисляем */
            case ADD:
                stack[scount - 1] += stack[scount];
                break;

            case SUB:
                stack[scount - 1] -= stack[scount];
                break;

            case MUL:
                stack[scount - 1] *= stack[scount];
                break;

            case DIV:
                if (stack[scount] != 0) {
                    stack[scount - 1] /= stack[scount];
                    break;
                } else {
                    fprintf(stderr, "Деление на ноль!\n");
                    return(1);
                }

            /* Обработка ошибок */
            case SUF:
                fprintf(stderr, "Недостаточно операндов!\n");
                return(1);

            case SOF:
                fprintf(stderr, "Переполнение стека!\n");
                return(1);

            case UNK:
                fprintf(stderr, "Неопознанный аргумент!\n");
                return(1);
        }
    }

    /* Вывести результат */
    auto int i;
    for (i = 0; i < scount; i++) printf("%0.3f\n", stack[i]);

    return(0);
}

int parse(char *s)
{
    double tval = 0;
    char * endptr;

    /* Распознаем знаки арифметических операций */
    switch (*s) {
        case '-':
            /* Если минус является первым и не последним символом аргумента,
             * значит пользователь ввел отрицательное число и опознавать его
             * как операцию вычитания не нужно */
            if (*(s+1) != '\0') break;
            if (scount >= 2) {
                scount -= 1;
                return(SUB);
            }
            else return(SUF);

        case '+':
            if (scount >= 2) {
                scount -= 1;
                return(ADD);
            }
            else return(SUF);

        case 'x':
            if (scount >= 2) {
                scount -= 1;
                return(MUL);
            }
            else return(SUF);

        case '/':
            if (scount >= 2) {
                scount -= 1;
                return(DIV);
            }
            else return(SUF);
    }

    errno = 0;

    /* Пытаемся сконвертировать строковый аргумент в число */
    tval = strtod(s, &endptr);

    /* Вернуть ошибку `неопознанный аргумент' в случае неудачи */
    if (errno != 0 || *endptr != '\0') return(UNK);

    /* Проверяем, есть ли свободное место в стеке
     * и сохраняем в нем операнд, иначе возвращаем ошибку переполнения */
    if (scount < STKDPTH) stack[scount++] = tval;
    else return(SOF);

    return(VAL);
}

Delphi[править]

program calc;
{$APPTYPE console}

type
  Real = double;

const
  prs = '+-*/(';
  pri: array [1 .. 5] of byte = (1, 1, 2, 2, 0);

var
  s1, s2: String;
  q: array [0 .. 500] of Real;
  w: array [0 .. 500] of Char;
  n, len, len2: Cardinal;
  t: Real;
  ch: Char;

procedure Push(x: Real);
begin
  Inc(len);
  q[len] := x;
end;

function Pop: Real;
begin
  Pop := q[len];
  q[len] := 0;
  Dec(len);
end;

procedure PushC(x: Char);
begin
  Inc(len2);
  w[len2] := x;
end;

function Popc: Char;
begin
  Popc := w[len2];
  w[len2] := #0;
  Dec(len2);
end;

function Oper(s1, s2: Real; s3: Char): Real;
var
  x, y, z: Real;
begin
  x := s1;
  y := s2;
  case s3 of
    '+': z := x + y;
    '-': z := x - y;
    '*': z := x * y;
    '/': z := x / y;
  end;
  Oper := z;
end;

procedure PreChange(var s: String);
var
  i: Cardinal;
begin
  if s[1] = '-' then
    s := '0' + s;
  i := 1;
  while i <= n do
    if (s[i] = '(') and (s[i + 1] = '-') then
      insert('0', s, i + 1)
    else
      Inc(i);
end;

function Change(s: String): String;
var
  i: Cardinal;
  rezs: String;
  c: Boolean;
begin
  c := false;
  for i := 1 to n do
    begin
      if not(s[i] in ['+', '-', '*', '/', '(', ')']) then
        begin
          if c then
            rezs := rezs + ' ';
          rezs := rezs + s[i];
          c := false;
        end
      else
        begin
          c := true;
          if s[i] = '(' then
            PushC(s[i])
          else
            if s[i] = ')' then
              begin
                while w[len2] <> '(' do
                  begin
                    rezs := rezs + ' ' + Popc;
                  end;
                Popc;
              end
            else
              if s[i] in ['+', '-', '*', '/'] then
                begin
                  while pri[Pos(w[len2], prs)] >= pri[Pos(s[i], prs)] do
                    rezs := rezs + ' ' + Popc;
                  PushC(s[i]);
                end;
        end;
    end;
  while len2 <> 0 do
    rezs := rezs + ' ' + Popc;
  Change := rezs;
end;

function Count(s: String): Real;
var
  ss: String;
  x, s1, s2: Real;
  chh, s3: Char;
  p, i, j: Cardinal;
  tmp: Integer;
begin
  i := 0;
  repeat
    j := i + 1;
    repeat
      Inc(i)
    until s[i] = ' ';
    ss := copy(s, j, i - j);
    chh := ss[1];
    if not(chh in ['+', '-', '*', '/']) then
      begin
        Val(ss, p, tmp);
        Push(p);
      end
    else
      begin
        s2 := Pop;
        s1 := Pop;
        s3 := chh;
        Push(Oper(s1, s2, s3));
      end;
  until i >= n;
  x := Pop;
  Count := x;
end;

procedure WriteL(x: Real);
var
  y, a, b: Cardinal;
  q: Real;
begin
  y := Trunc(x);
  b := 0;
  if Abs(x - y) < (1E-12) then
    Writeln(y)
  else
    begin
      if y > 0 then
        a := round(ln(y) / ln(10)) + 1
      else
        a := 1;
      q := x;
      repeat
        q := q * 10;
        Inc(b);
      until Abs(q - Trunc(q)) < (1E-12);
      Writeln(x:a + b:b);
    end;
end;

begin
  repeat
    Writeln('Enter expression');
    Readln(s1);
    n := Length(s1);
    PreChange(s1);
    n := Length(s1);
    s2 := Change(s1);
    if s2[1] = ' ' then
      delete(s2, 1, 1);
    s2 := s2 + ' ';
    n := Length(s2);
    t := Count(s2);
    WriteL(t);
    Writeln('One more expression?(Y/N)');
    Readln(ch);
  until UpCase(ch) = 'N';

end.

Глагол[править]

ОТДЕЛ ОПН;
    ПЕР
        Стек: РЯД 20H ИЗ ЗНАК;

    ЗАДАЧА Преимущество(зн: ЗНАК): ЦЕЛ;
    УКАЗ
        ВЫБРАТЬ зн ИЗ
                '*', '/': ВОЗВРАТ 3
                | '-', '+': ВОЗВРАТ 2
                | '(', ')': ВОЗВРАТ 1
        ИНАЧЕ
                ВОЗВРАТ 0
        КОН
    КОН Преимущество;
    
    ЗАДАЧА Добавить(зн: ЗНАК);
    УКАЗ
        ЕСЛИ ДЛИНА(Стек) = РАЗМЕР(Стек) ТО
        	Вывод.Цепь("Ошибка: стек переполнен.");
        	СТОП(0)
        КОН;
        Стек[ДЛИНА(Стек)] := зн
    КОН Добавить;
    
    ЗАДАЧА Удалить(): ЗНАК;
    ПЕР
        зн: ЗНАК;
    УКАЗ
        ЕСЛИ ДЛИНА(Стек) = 0 ТО
                Вывод.Цепь("Ошибка: стек пуст.");
                СТОП(0)
        КОН;
        зн := Стек[ДЛИНА(Стек)-1];
        Стек[ДЛИНА(Стек)-1] := 0X;
        ВОЗВРАТ зн
    КОН Удалить;
    
    ЗАДАЧА Перевести(вход-, выход+: РЯД ИЗ ЗНАК);
    ПЕР
        сч1, сч2: УЗКЦЕЛ;
        зн: ЗНАК;
    УКАЗ
        зн := 0X; сч2 := 0;
        ОТ сч1 := 0 ДО ДЛИНА(вход)-1 ВЫП
            ЕСЛИ вход[сч1] = ")" ТО
                ПОКА Стек[ДЛИНА(Стек)-1] # "(" ВЫП
                    выход[сч2] := Удалить();
                    УВЕЛИЧИТЬ(сч2)
                КОН;
                зн := Удалить()
            АЕСЛИ вход[сч1] = "(" ТО
                Добавить(вход[сч1])
            АЕСЛИ (вход[сч1] = "+") ИЛИ (вход[сч1] = "-") ИЛИ (вход[сч1] = "/") ИЛИ (вход[сч1] = "*") ТО
                ЕСЛИ ДЛИНА(Стек) = 0 ТО Добавить(вход[сч1]) ИНАЧЕ
                    ЕСЛИ Преимущество(вход[сч1]) > Преимущество(Стек[ДЛИНА(Стек)-1]) ТО
                        Добавить(вход[сч1])
                    ИНАЧЕ
                        ПОКА (ДЛИНА(Стек) # 0) И (Преимущество(вход[сч1]) <= Преимущество(Стек[ДЛИНА(Стек)-1])) ВЫП
                            выход[сч2] := Удалить(); УВЕЛИЧИТЬ(сч2)
                        КОН;
                        Добавить(вход[сч1])
                    КОН
                КОН
            АЕСЛИ Знак.Буква(вход[сч1]) ТО
                выход[сч2] := вход[сч1];
                УВЕЛИЧИТЬ(сч2)
            КОН
        КОН;
        ПОКА ДЛИНА(Стек) # 0 ВЫП
            выход[сч2] := Удалить();
            УВЕЛИЧИТЬ(сч2)
        КОН
    КОН Перевести;
КОН ОПН.

PHP[править]

Пример использования класса Calculate

<?php

require_once __DIR__ . '/Calculate.php';
$calc = new Calculate('3 * ((-25 - 10 * -2 ^ 2 / 4) * (4 + 5)) / 2');
if ($calc->postfixString) {
    echo PHP_EOL;
    echo 'Строка в постфиксной записи (~ - это унарный минус): ' . $calc->postfixString . PHP_EOL . PHP_EOL;
    echo 'Результат вычисления постфиксной записи: ' . $calc->result . PHP_EOL . 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 => 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
    ];

    private array $stack = [];
    private array $outString = [];

    /**
     * @var float|string
     */
    public $result;
    public string $postfixString = '';

    public function __construct(string $expression)
    {
        try {
            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('Ошибка! В строке могут быть только цифры, скобки, и операторы +, -, *, /, ^');
            }
            $this->createOutString($expression);
            $this->postfixString = implode(' ', $this->outString);
            $this->result = $this->calcFromOutString();
        } catch (Exception $e) {
            $this->result = $e->getMessage();
        }
    }

    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 ($item === '-') {
                $arr = [self::PLUS, self::MULTIPLICATION, self::EXPONENTIATION, self::MINUS, self::DIVISION, self::OPEN_BRACKET];
                if ($left === null || in_array($left, $arr)) {
                    $item = self::UNARY_MINUS;
                }
            }

            if (is_numeric($item) || $item === '.') {
                if ($item === '.') {
                    if ($left === null || $right === null || !is_numeric($left) || !is_numeric($right)) {
                        throw new DomainException('Неверное дробное выражение!');
                    }
                }
                $number .= $item;
                if (!is_numeric($right)) {
                    $this->outString[] = (float)$number;
                    $number = null;
                }
                continue;
            }

            if (in_array($item, array_keys(self::PRIORITY))) {
                if ($item === self::OPEN_BRACKET && is_numeric($left)) {
                    $this->addToStackAndPushFromStack(self::MULTIPLICATION);
                }
                $this->addToStackAndPushFromStack($item);
                if ($item === self::CLOSE_BRACKET && (is_numeric($right) || $right === self::OPEN_BRACKET)) {
                    $this->addToStackAndPushFromStack(self::MULTIPLICATION);
                }
            }
        }
        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;
    }

    /**
     * @return float
     * Вычисляем из постфиксной записи
     */
    private function calcFromOutString(): float
    {
        $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);
        }
        return $stack[0];
    }
}

C#[править]

Функция toRPN работает некорректно. Можно проверить на формуле 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Должно быть: 3 4 2 * 1 5 − 2 3 ^ ^ / + Функция отдает: 3 4 2 * 1 5 - 2 ^ 3 ^ / +. Да нет, как раз результат 3 4 2 * 1 5 - 2 ^ 3 ^ / + является верным
Некорректно работает для Input = "5"

//  Преобразование инфиксной записи к постфиксной
//      i.dudinov@gmail.com
//  Добавлена функция result для вывода результата
// kiss_a@bk.ru
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace PostfixNotation
{
    public class PostfixNotationExpression
    {
        public PostfixNotationExpression()
        {
            operators = new List<string>(standart_operators);
            
        }
        private List<string> operators;
        private List<string> standart_operators =
            new List<string>(new string[] { "(", ")", "+", "-", "*", "/", "^" });

        private IEnumerable<string> Separate(string input)
        {            
            int pos = 0;
            while (pos < input.Length)
            {
                string s = string.Empty + input[pos];
                if (!standart_operators.Contains(input[pos].ToString()))
                {
                    if (Char.IsDigit(input[pos]))
                        for (int i = pos + 1; i < input.Length &&
                            (Char.IsDigit(input[i]) || input[i] == ',' || input[i] == '.'); i++)
                            s += input[i];
                    else if (Char.IsLetter(input[pos]))
                        for (int i = pos + 1; i < input.Length &&
                            (Char.IsLetter(input[i]) || Char.IsDigit(input[i])); i++)
                            s += input[i];
                }
                yield return s;
                pos += s.Length;
            }
        }
        private byte GetPriority(string s)
        {
            switch (s)
            {
                case "(":
                case ")":
                    return 0;
                case "+":
                case "-":
                    return 1;
                case "*":
                case "/":
                    return 2;
                case "^":
                    return 3;
                default:
                    return 4;
            }
        }

        public string[] ConvertToPostfixNotation(string input)
        {
            List<string> outputSeparated = new List<string>();
            Stack<string> stack = new Stack<string>();
            foreach (string c in Separate(input))
            {
                if (operators.Contains(c))
                {
                    if (stack.Count > 0 && !c.Equals("("))
                    {
                        if (c.Equals(")"))
                        {
                            string s = stack.Pop();
                            while (s != "(")
                            {
                                outputSeparated.Add(s);
                                s = stack.Pop();
                            }
                        }
                        else if (GetPriority(c) > GetPriority(stack.Peek()))
                            stack.Push(c);
                        else
                        {
                            while (stack.Count > 0 && GetPriority(c) <= GetPriority(stack.Peek()))
                                outputSeparated.Add(stack.Pop());
                            stack.Push(c);
                        }
                    }
                    else
                        stack.Push(c);
                }
                else
                    outputSeparated.Add(c);
            }
            if (stack.Count > 0)
                foreach (string c in stack)
                    outputSeparated.Add(c);

            return outputSeparated.ToArray();
        }
        public decimal result(string input)
        {
            Stack<string> stack = new Stack<string>();
            Queue<string> queue = new Queue<string>(ConvertToPostfixNotation(input));
            string str = queue.Dequeue();
            while (queue.Count >= 0)
            {
                if (!operators.Contains(str))
                {
                    stack.Push(str);
                    str = queue.Dequeue();
                }
                else
                {
                    decimal summ = 0;
                    try
                    {
                        
                        switch (str)
                        {

                            case "+":
                                {
                                    decimal a = Convert.ToDecimal(stack.Pop());
                                    decimal b = Convert.ToDecimal(stack.Pop());
                                    summ = a + b;
                                    break;
                                }
                            case "-":
                                {
                                    decimal a = Convert.ToDecimal(stack.Pop());
                                    decimal b = Convert.ToDecimal(stack.Pop());
                                    summ=b-a;
                                    break;
                                }
                            case "*":
                                {
                                    decimal a = Convert.ToDecimal(stack.Pop());
                                    decimal b = Convert.ToDecimal(stack.Pop());
                                    summ = b * a;
                                    break;
                                }
                            case "/":
                                {
                                    decimal a = Convert.ToDecimal(stack.Pop());
                                    decimal b = Convert.ToDecimal(stack.Pop());
                                    summ = b / a;
                                    break;
                                }
                            case "^":
                                {
                                    decimal a = Convert.ToDecimal(stack.Pop());
                                    decimal b = Convert.ToDecimal(stack.Pop());
                                    summ = Convert.ToDecimal(Math.Pow(Convert.ToDouble(b), Convert.ToDouble(a)));
                                    break;
                                }
                        }
                    }
                    catch (Exception ex)
                    {
                        MessageBox.Show(ex.Message);
                    }
                    stack.Push(summ.ToString());
                    if (queue.Count > 0)
                        str = queue.Dequeue();
                    else
                        break;
                }
                
            }
            return Convert.ToDecimal(stack.Pop());
        }
    }

}

Ruby[править]

# Преобразование к польской записи
# <oskin@rambler.ru>

def opz(iStr, stack)
  priority = Hash["(" => 0, "+" => 1, "-" => 1, "*" => 2, "/" => 2, "^" => 3]
  case iStr
    when /^\s*([^\+\-\*\/\(\)\^\s]+)\s*(.*)/ then $1 + " " + opz($2, stack)
    when /^\s*([\+\-\*\/\^])\s*(.*)/
      if (stack.empty? or priority[stack.last] < priority[$1]) then opz($2, stack.push($1))
      else stack.pop + " " + opz(iStr, stack) end
    when /^\s*\(\s*(.*)/ then opz($1, stack.push("("))
    when /^\s*\)\s*(.*)/
      if stack.empty? then raise "Error: Excess of closing brackets." 
      elsif priority[head = stack.pop] > 0 then head + " " + opz(iStr, stack)
      else opz($1, stack) end
    else if stack.empty? then "" 
         elsif priority[stack.last] > 0 then stack.pop + " " + opz(iStr, stack) 
         else raise "Error: Excess of opening brackets." end
  end
end

while a = gets
  begin
    puts opz(a, [])
  rescue Exception => e
    puts e.message
  end
end

Javascript[править]

const operators = {
    '+': (x, y) => x + y,
    '-': (x, y) => x - y,
    '*': (x, y) => x * y,
    '/': (x, y) => x / y
};

let evaluate = (expr) => {
    let stack = [];
    
    expr.split(' ').forEach((token) => {
        if (token in operators) {
            let [y, x] = [stack.pop(), stack.pop()];
            stack.push(operators[token](x, y));
        } else {
            stack.push(parseFloat(token));
        }
    });

    return stack.pop();
};

Python[править]

import operator

OPERATORS = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}


def polska(srt):
    stack = []
    lst = list(srt)
    for i in srt:
        if i.isdigit():
            stack.append(i)
            lst.remove(i)
        else:
            cnt1, cnt2 = stack.pop(), stack.pop()
            stack.append(OPERATORS[i](int(cnt2), int(cnt1)))
            lst.remove(i)
    return stack.pop()