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

Примеры реализации

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

C

//copyright (c) Prog Land
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void)
{
        float stack[70];
        float res;
        int m = 0;
        char query[100];
 
        printf("Введите выражение: ");
        gets(query);
 
        for (int i = 0; i < strlen(query); i++)
        {
                if (query[i] >= '0' && query[i] <= '9')
                {
                        stack[m] = query[i] - '0';
                        m++;
                        continue;
                }
 
                switch (query[i])
                {
                        case '+':
                        {
                                res = stack[m - 2] + stack[m - 1];
                                break;
                        }       
                        case '-':
                        {
                                res = stack[m - 2] - stack[m - 1];
                                break;
                        }
                        case '*':
                        {
                                res = stack[m - 2] * stack[m - 1];
                                break;
                        }
                        case '/':
                        {
                                res = stack[m - 2] / stack[m - 1];
                                break;
                        }
                }
 
                stack[m - 2] = res;
                m--;
        }
 
        printf("Ответ: %f", res);
        getchar();
 
        return 0;
}

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.

PHP

$expr = '3 4 5 * + 7 + 4 6 - /';
 
echo calc($expr);
 
function calc($str)
{
        $stack = array();
 
        $token = strtok($str, ' ');
 
        while ($token !== false)
        {
                if (in_array($token, array('*', '/', '+', '-')))
                {
                        if (count($stack) < 2)
                                throw new Exception("Недостаточно данных в стеке для операции '$token'");
                        $b = array_pop($stack);
                        $a = array_pop($stack);
                        switch ($token)
                        {
                                case '*': $res = $a*$b; break;
                                case '/': $res = $a/$b; break;
                                case '+': $res = $a+$b; break;
                                case '-': $res = $a-$b; break;
                        }
                        array_push($stack, $res);
                } elseif (is_numeric($token))
                {
                                array_push($stack, $token);
                } else
                {
                        throw new Exception("Недопустимый символ в выражении: $token");
                }
 
                $token = strtok(' ');
        }
        if (count($stack) > 1)
                throw new Exception("Количество операторов не соответствует количеству операндов");
        return array_pop($stack);
}

C#

//  Преобразование инфиксной записи к постфиксной
//  с учетом унарных операций (функций), коллекция имен которых передается 
//  в конструктор класса
//      i.dudinov@gmail.com
 
using System;
using System.Collections.Generic;
 
namespace PostfixNotation
{
    public class PostfixNotationExpression
    {
        public PostfixNotationExpression(IEnumerable<string> funcNames)
        {
            operators = new List<string>(funcNames);
            operators.AddRange(standart_operators);
        }
        private List<string> operators;
        private List<string> standart_operators =
            new List<string>(new string[] { "(", ")", "+", "-", "*", "/", "^" });
 
        private IEnumerable<string> Separate(string input)
        {
            List<string> inputSeparated = new List<string>();
            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 "(":
                    return 0;
                case ")":
                    return 1;
                case "+":
                    return 2;
                case "-":
                    return 3;
                case "*":
                case "/":
                    return 4;
                case "^":
                    return 5;
                default:
                    return 6;
            }
        }
 
        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 string.Join("", outputSeparated.ToArray());
        }
    }
}

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

function toRPN(str)
{
    var ret = [];
    var token = '';
    var operators = 
    {
        '(':{'priority':4},
        ')':{'priority':4},
        '^':{'priority':3},
        '*':{'priority':2},
        '/':{'priority':2},
        '+':{'priority':1},
        '-':{'priority':1}
    };
 
    var stack = [];
    for(ind in str)
    {
        var ch = str[ind];
        if(ch == ' ')
        {
            if(token.length > 0)
                ret.push(token);
 
            token = '';
            continue;
        }
 
        if(ch in operators)
        {
            if(token.length > 0)
                ret.push(token);
 
            token = '';
            if(ch == ')')
            {
                var t = '';
                while( (t=stack.pop()) != '(' )
                {
                    ret.push(t);
                }
            }
            else
            {
                var t = stack[stack.length - 1];
                if(t != 'undefined' && t != null)
                {
                    if ( t != '(' && operators[t].priority >= operators[ch].priority)
                    {
                        for(;;)
                        {
                            t = stack[stack.length - 1];
                            if(t == undefined || t == null || operators[t].priority < operators[ch].priority)
                                break;
                            t = stack.pop();
                            ret.push(t);
                        }
                    }
                }
                stack.push(ch);
            }
        }
        else
        {
            token += str[ind];
        }
    }
 
    if(token.length > 0)
        ret.push(token);
 
    while(stack.length!=0)
        ret.push(stack.pop());
 
    return ret;
}
 
function calcRPN(arrRPN)
{
    var stack = [];
    var a = 0;
    var b = 0;
 
    for(var i in arrRPN)
    {
        var token = arrRPN[i];
 
        if(!(token in operators))
        {
            stack.push(token);
            continue;
        }
 
        b = stack.pop();
        a = stack.pop();
 
        switch(token)
        {
            case '+':
                stack.push(Number(a) + Number(b));
                break;
            case '-':
                stack.push(Number(a) - Number(b));
                break;
            case '*':
                stack.push(Number(a) * Number(b));
                break;
            case '/':
                stack.push(Number(a) / Number(b));
                break;
            case '^':
                stack.push(Math.pow(Number(a), Number(b)));
        }
    }
 
    return stack.pop();
}