INFIX TO POSTFIX AND POSTFIX EVALUATION (PYTHON)
Stack Expressions : INFIX TO POSTFIX AND POSTFIX EVALUATION
Infix
to Postfix Conversion Infix expression: The expression of the form a
op b. When an operator is in-between every pair of operands. Postfix
expression: The expression of the form a b op. When an operator is
followed for every pair of operands. Algorithm: 1. Scan the infix
expression from left to right. 2. If the scanned character is an
operand, output it. 3. Else, 3.1 If the precedence of the scanned
operator is greater than the precedence of the operator in the
stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
3.2 Else, Pop all the operators from the stack which are greater than
or equal to in precedence than that of the scanned operator. After
doing that Push the scanned operator to the stack. (If you encounter
parenthesis while popping then stop there and push the scanned
operator in the stack.) 4. If the scanned character is an ‘(‘, push it
to the stack. 5. If the scanned character is an ‘)’, pop the stack and
and output it until a ‘(‘ is encountered, and discard both the
parenthesis. 6. Repeat steps 2-6 until infix expression is scanned. 7.
Print the output 8. Pop and output from the stack until it is not empty.
Program: OPERATORS = set(['+', '-', '*', '/', '(', ')']) PRIORITY =
{'+':1, '-':1, '*':2, '/':2} def infix_to_postfix(formula): stack =
[] # only pop when the coming op has priority output = '' for
ch in formula: if ch not in OPERATORS: output += ch
elif ch == '(': stack.append('(') elif ch ==
')': while stack and stack[-1] != '(':
output += stack.pop() stack.pop() # pop '(' else:
while stack and stack[-1] != '(' and PRIORITY[ch] <
PRIORITY[stack[-1]]: output += stack.pop()
stack.append(ch) # leftover while stack: output += stack.pop()
print (output) infix_to_postfix('a+b') OUTPUT: ab+
Postfix
Evaluation The procedure for getting the result is: 1. Convert the
expression in post-fix notation. 2. Push the operands into the stack in
the order they are appear. 3. When any operator is encountered then pop
two topmost operands for executing the operation. 4. After execution
push the result obtained into the stack. 5. After the complete execution
of expression the final result remains on the top of the stack.
Program: OPERATORS = set(['+', '-', '*', '/', '(', ')'])
PRIORITY = {'+':1, '-':1, '*':2, '/':2} def evaluate_postfix(formula):
stack = [] for ch in formula: if ch not in OPERATORS:
stack.append(float(ch)) else: b =
stack.pop() a = stack.pop() c = {'+':a+b,
'-':a-b, '*':a*b, '/':a/b}[ch] stack.append(c) print
(stack[-1]) evaluate_postfix('14+') OUTPUT: 5.0
Comments
Post a Comment
Please do not enter any spam link in the comment box.