A simplified Python algorithm for converting infix expressions to postfix expressions using Dijkstra’s “shunting-yard” algorithm. We omit support for functions and their arguments but support parenthesis as expected. For the purpose of this example, we support simple mathematical expressions.
OP_LPAREN = '('
OP_RPAREN = ')'
OP_MULTIPLY = '*'
OP_DIVIDE = '/'
OP_ADD = '+'
OP_SUBTRACT = '-'
OPERATORS_S = set([
OP_MULTIPLY,
OP_DIVIDE,
OP_ADD,
OP_SUBTRACT,
OP_LPAREN,
OP_RPAREN,
])
PRECEDENCE = {
OP_MULTIPLY: 7,
OP_DIVIDE: 7,
OP_ADD: 5,
OP_SUBTRACT: 5,
OP_LPAREN: 1,
OP_RPAREN: 1,
}
LEFT_ASSOCIATIVE_S = set([
OP_MULTIPLY,
OP_DIVIDE,
OP_ADD,
OP_SUBTRACT,
OP_LPAREN,
OP_RPAREN,
])
def _convert(expression_phrase):
expression_phrase = expression_phrase.replace(' ', '')
stack = []
output = []
for c in expression_phrase:
if c not in OPERATORS_S:
# It's an operand.
output += [c]
elif c not in (OP_LPAREN, OP_RPAREN):
# It's an operator. Pop-and-add all recent operators that win over
# the current operator via precendence/associativity.
current_prec = PRECEDENCE[c]
is_left_assoc = c in LEFT_ASSOCIATIVE_S
while len(stack):
top_value = stack[-1]
top_prec = PRECEDENCE[top_value]
if is_left_assoc is True and current_prec <= top_prec or \
is_left_assoc is False and current_prec < top_prec:
stack.pop()
output += [top_value]
else:
break
stack.append(c)
elif c == OP_LPAREN:
# It's a left paren.
stack.append(c)
else: #if c == OP_RPAREN:
# It's a right paren. Pop-and-add everything since the last left
# paren.
found = False
while len(stack):
top_value = stack.pop()
if top_value == OP_LPAREN:
found = True
break
output += [top_value]
if found is False:
raise ValueError("Mismatched parenthesis (1).")
if stack and stack[-1] in (OP_LPAREN, OP_RPAREN):
raise ValueError("Mismatched parenthesis (2).")
# Flush everything left on the stack.
while stack:
c = stack.pop()
output += [c]
return ' '.join(output)
def _main():
infix_phrase = 'a * (b * c) / d * (e + f + g) * h - i'
print(infix_phrase)
postfix_phrase = _convert(infix_phrase)
print(postfix_phrase)
if __name__ == '__main__':
_main()
Output:
a * (b * c) / d * (e + f + g) * h - i a b c * * d / e f + g + * h * i -
You may download the code here.
Random Engineering 
You must be logged in to post a comment.