Convert Łukasiewicz's Polish notation to standard logical infix notation.

polish2infix.py

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

"""
File: polish2infix.py
Author: Alexander Klapheke
Email: alexklapheke@gmail.com
Github: https://github.com/klapheke
Licence: MIT Licence

Description: Convert Łukasiewicz's Polish notation to standard infix notation
(see <http://plato.stanford.edu/entries/lukasiewicz/polish-notation.html>).
Uppercase letters are interpreted as 1-place functions, unless defined as
operators. Lowercase letters are intepreted as (propositional) variables.
Accepts Greek and Latin characters. Does not sanity-check formulas.

Usage: python polish2infix.py 'CCCCCttpqCrsCCspCuCrp'
       echo 'CCCCCttpqCrsCCspCuCrp' | python polish2infix.py -
"""

import sys

def _replace_symbol(symbol):
    symbols = { u"N": u"¬" # negation
              , u"K": u"∧" # conjunction
              , u"A": u"∨" # disjunction
              , u"J": u"⊕" # exclusive disjunction
              , u"C": u"→" # implication
              , u"B": u"←" # reverse implication
              , u"E": u"↔" # biimplication
              , u"D": u"↑" # sheffer stroke (nand)
              , u"X": u"↓" # peirce arrow (nor)
              , u"V": u"⊤" # tautology
              , u"O": u"⊥" # contradiction
              , u"Σ": u"∃" # existential quantification (can also use S)
              , u"Π": u"∀" # universal quantification (can also use P)
              , u"M": u"⋄" # modal possibility
              , u"L": u"◻" # modal necessity (L can also signify nonimplication ↛)
              , u"T": u"T" # true at time
              , u"S": u"S" # since
              , u"U": u"U" # until
              }
    return symbols.get(symbol,symbol)

def _throw(err):
    sys.stderr.write('Error: %s\n' % err)
    sys.exit(2)

def polish2infix(s, always_use_parens=False, order_of_ops=None):
    """Convert Polish notation to infix notation.

    Usage: polish2infix(string, [always_use_parens, order_of_ops])

    Parameters:
        always_use_parens: use parentheses even if order of ops disambiguates
        order_of_ops:      list of two-place Polish operators from highest to
                           lowest precedence
    """

    stack  = ['']
    string =  ''
    scope  =  ''

    if order_of_ops is None:
         order_of_ops = ['K','X','D','J','A','C','B','E']
    order_of_ops.insert(0, scope)

    for token in unicode(s,'utf-8'):

        # 2-place infix operators
        if token in u"KACEDJBX":
            if always_use_parens or order_of_ops.index(token) >= order_of_ops.index(scope):
                stack.append(')')
                string += '('
            stack.append(_replace_symbol(token))
            scope = token

        # 1-place prefix operators
        elif token in u"NML":
            if always_use_parens:
                stack.append(')')
                string += '('
            string += _replace_symbol(token)
            scope = ''

        # quantifiers
        elif token in u"ΣΠ":
            stack.append(']')
            stack.append('[')
            string += _replace_symbol(token)

        # 2-place prefix operators (until, since, temporal predication)
        elif token in u"UST":
            stack.append(')')
            stack.append(',')
            string += _replace_symbol(token)
            string += '('

        # 1-place functions (isupper() and islower() don't work with Greek)
        elif token in u"FGHIPQRWYZΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΡΤΥΦΧΨΩ":
            stack.append(')')
            string += _replace_symbol(token)
            string +='('

        # 0-place operators (propositions)
        elif token in u"VOabcdefghijklmnopqrstuvwxyzαβγδεζηθικλμνξοπρστυφχψω":
            string += _replace_symbol(token)

            last = ')'
            while last == ')' or last == ']':
                try:
                    last = stack.pop()
                except IndexError:
                    _throw('Malformed expression.')
                string += last

        elif token not in ' \n':
            _throw('Illegal symbol in string.')

    if len(stack) > 0:
        _throw('Malformed expression.')

    return string

if __name__ == '__main__':
    try:
        string = sys.argv[1]
    except IndexError:
        _throw('Please specify a string.')
    if string == '-':
        string = sys.stdin.read()
    print polish2infix(string)