polish.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from enum import IntEnum, unique


@unique
class Priority(IntEnum):
    Lowest = 0
    Low = 1
    Average = 2
    High = 3
    VeryHigh = 4


operators = {
    '!': {'priority': Priority.VeryHigh, 'arity': 1},
    '^': {'priority': Priority.High, 'arity': 2},
    '*': {'priority': Priority.Average, 'arity': 2},
    '/': {'priority': Priority.Average, 'arity': 2},
    '+': {'priority': Priority.Low, 'arity': 2},
    '-': {'priority': Priority.Low, 'arity': 2},
    '(': {'priority': Priority.Lowest, 'arity': 2},
    ')': {'priority': Priority.Lowest, 'arity': 2}
}


def priority(op):
    """Return priority of operator $op as int."""
    return int(operators[op]['priority'])


def checkBrackets(exp):
    """Check brackets into expression $exp."""
    brackets = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    bracketsOut = [brackets[br] for br in brackets]

    stack = []
    for char in exp:
        if char in brackets:
            stack += char
        elif char in bracketsOut:
            if stack and brackets[stack[-1]] == char:
                stack.pop()
            else:
                return False
    return not stack


def toExpression(text):
    """Return expression from text as list."""
    exp = []
    num = ''
    var = ''
    unaryNext = True

    for char in text:
        if char.isdigit():
            num += char
        else:
            if num:
                exp.append(int(num))
                num = ''
                unaryNext = False

            if char.isalpha():
                var += char
            elif var:
                exp.append(var)
                var = ''
                unaryNext = False

            if char in operators:
                if unaryNext:
                    if char == '-':
                        char = '!'
                exp += char
                unaryNext = True if char != ')' else False
    if num:
        exp.append(int(num))
    if var:
        exp.append(var)

    return exp


def evaluate(operands, operator):
    """"Returns the value of the operation applied to operands."""
    arity = operators[operator]['arity']
    if len(operands) != arity:
        print('Error: wrong count operands for operator {op}.'
              'Expected {expected} args, three is a {three}.'.format(
            op=operator,
            expected=arity,
            three=len(operands)
        ))
        return None

    if operator == '^':
        return operands[0] ** operands[1]
    elif operator == '*':
        return operands[0] * operands[1]
    elif operator == '/':
        return operands[0] / operands[1]
    elif operator == '+':
        return operands[0] + operands[1]
    elif operator == '-':
        return operands[0] - operands[1]
    elif operator == '!':
        return -operands[0]
    else:
        return None


def calculateRPN(exp):
    stack = []

    for token in exp:
        if isinstance(token, int):
            stack.append(token)
        elif token in operators:
            arity = operators[token]['arity']
            operands = [stack.pop() for i in range(arity)][::-1]
            stack.append(evaluate(operands, token))

    return stack.pop()


def toRPN(exp):
    """Return expression in reverse Polish notation (RPN).

    The complexity of the algorithm O(n)."""

    out = []
    stack = []

    for token in exp:
        if token in operators:
            if token == '(':
                stack += token
            elif token == ')':
                while stack and stack[-1] != '(':
                    out += stack.pop()
                if not stack:
                    print('Error: expected `(`')
                else:
                    stack.pop()
            else:
                while stack and (operators[stack[-1]]['arity'] > 1 and priority(token) <= priority(stack[-1]) or
                                             operators[stack[-1]]['arity'] == 1 and priority(token) < priority(stack[-1])):
                    out += stack.pop()
                stack += token
        else:
            out.append(token)

    while stack:
        if stack[-1] == '(':
            print('Error: expected `)`')
        out += stack.pop()

    return out


def calculateInfix(exp):
    """Returns the calculated value of the infix expression.

    This function evaluates the expression in a single pass
    using reverse polish notation and two stacks.
    The complexity of the algorithm O(n)."""

    out = []
    stack = []

    def calcLast():
        operator = stack.pop()
        arity = operators[operator]['arity']
        operands = [out.pop() for i in range(arity)][::-1]
        out.append(evaluate(operands, operator))

    for token in exp:
        if token in operators:
            if token == '(':
                stack += token
            elif token == ')':
                while stack and stack[-1] != '(':
                    calcLast()
                if not stack:
                    print('Error: expected `(`')
                else:
                    stack.pop()
            else:
                while stack and (operators[stack[-1]]['arity'] > 1 and priority(token) <= priority(stack[-1]) or
                                             operators[stack[-1]]['arity'] == 1 and priority(token) < priority(
                                         stack[-1])):
                    calcLast()
                stack += token
        else:
            out.append(token)

    while stack:
        if stack[-1] == '(':
            print('Error: expected `)`')
        calcLast()

    return out.pop()


def main():
    print('This programm calculate expression.\n')


def test():
    dataset = [
        {'exp': '10^2 + 20', 'val': 120},
        {'exp': '(1+2) * 4 + 3', 'val': 15},
        {'exp': '-10 + 20 - (-3 + 5) * 3', 'val': 4},
        {'exp': '-10 + -10', 'val': -20},
        {'exp': '-10 - -10', 'val': 0},
        {'exp': '1.5 + 2', 'val': 3.5},
        {'exp': '10^2+20', 'val': 120},
    ]

    for case in dataset:
        exp = toExpression(case['exp'])
        print('Test case:\n'
              '\tInput: {input}\n'
              '\tParse: {parse}\n'
              '\tCheck: {check}\n'
              '\tValue: {value}\n'.format(
            input=case['exp'],
            parse=' '.join(str(i) for i in exp),
            check=case['val'],
            value=calculateInfix(exp)
        ))


if __name__ == '__main__':
    main()
    test()