converting infix to prefix in python

Question

I am trying to write an Infix to Prefix Converter where e.g. I would like to convert this:

1 + ((C + A ) * (B - F))

to something like:

add(1, multiply(add(C, A), subtract(B, F)))

but I get this instead :

multiply(add(1, add(C, A), subtract(B, F)))

This is the code I have so far

postfix = []
temp = []
newTemp = []

def textOperator(s):
    if s is '+':
        return 'add('
    elif s is '-':
        return 'subtract('
    elif s is '*':
        return 'multiply('
    else:
        return ""

def typeof(s):
    if s is '(':
        return leftparentheses
    elif s is ')':
        return rightparentheses
    elif s is '+' or s is '-' or s is '*' or s is '%' or s is '/':
        return operator
    elif s is ' ':
        return empty    
    else :
        return operand                          

infix = "1 + ((C + A ) * (B - F))"

for i in infix :
    type = typeof(i)
    if type is operand:
        newTemp.append(i)
    elif type is operator:
        postfix.append(textOperator(i))
        postfix.append(newTemp.pop())
        postfix.append(', ')
    elif type is leftparentheses :
        newTemp.append(i)
    elif type is rightparentheses :
        next = newTemp.pop()
        while next is not '(':
            postfix.append(next)
            next = newTemp.pop()
            postfix.append(')')
            newTemp.append(''.join(postfix))
            while len(postfix) > 0 :
                postfix.pop()
    elif type is empty:
        continue
    print("newTemp = ", newTemp)
    print("postfix = ", postfix)

while len(newTemp) > 0 :
    postfix.append(newTemp.pop())
postfix.append(')')

print(''.join(postfix))

Can someone please help me figure out how I would fix this.

General comment: don't use `is`, use `==` instead. `==` compares by value, while `is` compares by identity. Two strings can have the same value but *NOT* the same identity. See: [Why does comparing strings in Python using either '==' or 'is' sometimes produce a different result?](http://stackoverflow.com/q/1504717/660921). — Martin Tournoij, Mar 02 '16 at 22:23

cdlane · Answer 1 · 2016-03-03T05:47:49.560

What I see, with the parenthetical clauses, is a recursive problem crying out for a recursive solution. The following is a rethink of your program that might give you some ideas of how to restructure it, even if you don't buy into my recursion argument:

import sys
from enum import Enum

class Type(Enum):  # This could also be done with individual classes
    leftparentheses = 0
    rightparentheses = 1
    operator = 2
    empty = 3
    operand = 4

OPERATORS = {  # get your data out of your code...
    "+": "add",
    "-": "subtract",
    "*": "multiply",
    "%": "modulus",
    "/": "divide",
}

def textOperator(string):
    if string not in OPERATORS:
        sys.exit("Unknown operator: " + string)
    return OPERATORS[string]

def typeof(string):
    if string == '(':
        return Type.leftparentheses
    elif string == ')':
        return Type.rightparentheses
    elif string in OPERATORS:
        return Type.operator
    elif string == ' ':
        return Type.empty
    else:
        return Type.operand

def process(tokens):

    stack = []

    while tokens:
        token = tokens.pop()

        category = typeof(token)

        print("token = ", token, " (" + str(category) + ")")

        if category == Type.operand:
            stack.append(token)
        elif category == Type.operator:
            stack.append((textOperator(token), stack.pop(), process(tokens)))
        elif category == Type.leftparentheses:
            stack.append(process(tokens))
        elif category == Type.rightparentheses:
            return stack.pop()
        elif category == Type.empty:
            continue

        print("stack = ", stack)

    return stack.pop()

INFIX = "1 + ((C + A ) * (B - F))"

# pop/append work from right, so reverse, and require a real list
postfix = process(list(INFIX[::-1]))

print(postfix)

The result of this program is a structure like:

('add', '1', ('multiply', ('add', 'C', 'A'), ('subtract', 'B', 'F')))

Which you should be able to post process into the string form you desire (again, recursively...)

PS: type and next are Python built-ins and/or reserved words, don't use them for variable names.

PPS: replace INFIX[::-1] with sys.argv[1][::-1] and you can pass test cases into the program to see what it does with them.

PPPS: like your original, this only handles single digit numbers (or single letter variables), you'll need to provide a better tokenizer than list() to get that working right.

converting infix to prefix in python

1 Answers1