Обратная польская запись: примеры реализации
Примеры реализации
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()