Suppose * and + have the same operator precedence level:
How would we interpret the infix expression A + B * C?
What are the operands of *? Are they B and C or A+B and C?
This expression is ambiguous.
What if the infix expression is A + (B * C) or (A + B) * C?
We can interpret it easily now because we know that the parenthesized expression is evaluated first.
We can remove ambiguity in the expression without using parentheses by converting infix expressions to postfix expressions.
In a postfix expression, operators follow their operands.
The postfix expression of A + B * C is A B C * +.
For example, in the A (B C *) + expression, * follows its operands, B C. Say B * C evaluates to K. Now, the expression becomes A K +. The + works the same way and follows its operands, A K.
Note: This shot implements the Shunting-yard algorithm. To Learn what the Shunting-yard algorithm is and how it works, see this shot: How to convert infix expressions to postfix.
Here is the program that uses the Shunting-yard algorithm to convert an infix expression to postfix:
import re# precedence level of supported operators.PRECEDENCE = {'^': 4, # highest precedence level'*': 3,'/': 3,'+': 2,'-': 2,'(': 1,}def infixToPostfix(expr):tokens = re.findall(r"(\b\w*[\.]?\w+\b|[\(\)\^\+\*\-\/])", expr)stack = []postfix = []for token in tokens:# If the token is an operand, then do not push it to stack.# Instead, pass it to the output.if token.isalnum():postfix.append(token)# If your current token is a right parenthesis# push it on to the stackelif token == '(':stack.append(token)# If your current token is a right parenthesis,# pop the stack until after the first left parenthesis.# Output all the symbols except the parentheses.elif token == ')':top = stack.pop()while top != '(':postfix.append(top)top = stack.pop()# Before you can push the operator onto the stack,# you have to pop the stack until you find an operator# with a lower priority than the current operator.# The popped stack elements are written to output.else:while stack and (PRECEDENCE[stack[-1]] >= PRECEDENCE[token]):postfix.append(stack.pop())stack.append(token)# After the entire expression is scanned,# pop the rest of the stack# and write the operators in the stack to the output.while stack:postfix.append(stack.pop())return ' '.join(postfix)# Let's convert infix to postfixexpressions = ['4*2+5*(2+1)/2', '4^2+5*(2+1)/2', 'A*(B+C)/D']for expr in expressions:print(infixToPostfix(expr))