Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.
Postfix Expression:
A postfix expression (also known as Reverse Polish Notation) consists of a single letter or operator followed by two postfix strings. Every postfix string that is longer than a single variable has two operands followed by an operator.
Algebraic expressions are represented using the Postfix notation. Because parenthesis is not required in postfix notation, expressions written in postfix form are evaluated faster than expressions written in infix notation. We’ve talked about infix-to-postfix conversion. The evaluation of postfix expressions is described in this post.
Examples:
Example1:
Input:
given postfix Expression=”91-82×63+”
Output:
The value of the given postfix expression = 9
Example2:
Input:
given postfix Expression="72/96-8+"
Output:
The value of the given postfix expression = 11
Given a Postfix Expression, the task is to evaluate the given postfix Expression using a stack in Python.
Program to Evaluate a Postfix Expression Using a Stack in Python
1)Algorithm:
Using a stack, we can quickly compute a postfix expression. The objective is to go from left to right via the given postfix phrase. Push the operand into the stack if the current character in the expression is an operand; otherwise, if the current character is an operator, pop the top two elements from the stack, evaluate them using the current operator, and push the result back into the stack. After we’ve processed all of the expression characters, there will be only one element in the stack carrying the value of a postfix expression.
2)Implementation(Static Input)
Approach:
- Give the postfix Expression as static input and store it in a variable.
- Pass the given postfix Expression as an argument to evalpostfix function
- Create a stack by taking an empty list which acts as a stack in this case to hold operands (or values).
- Traverse the given postfix expression using For loop.
- Do the following for each scanned element.
a) Push the element into the stack if it is a number.
b) Evaluate the operator and return the answer to the stack. - If the operator is ‘+’ then perform an addition operation on the top two elements by popping them out.
- If the operator is ‘-‘ then perform a subtraction operation on the top two elements by popping them out.
- If the operator is ‘/’ then perform a division operation on the top two elements by popping them out.
- If the operator is ‘*’ then perform a multiplication operation on the top two elements by popping them out.
- The only number in the stack is the final answer when the expression is traversed.
- The Exit of the Program.
Below is the implementation:
# Function which accepts the given postfix expression as argument # and evaluates the expression using stack and return the value def evaluatePostfix(givenExp): # Create a stack by taking an empty list which acts # as a stack in this case to hold operands (or values). givenstack = [] # Traverse the given postfix expression using For loop. for charact in givenExp: # Push the element into the given stack if it is a number. if charact.isdigit(): givenstack.append(int(charact)) # if the character is operator else: # remove the top two elements from the stack topfirst = givenstack.pop() topsecond = givenstack.pop() # Evaluate the operator and return the answer to the stack using append() funtion. # If the operator is '+' then perform an addition operation on # the top two elements by popping them out. if charact == '+': givenstack.append(topsecond + topfirst) # If the operator is '-' then perform a subtraction operation # on the top two elements by popping them out. elif charact == '-': givenstack.append(topsecond - topfirst) # If the operator is '/' then perform a division operation on # the top two elements by popping them out. elif charact == '×': givenstack.append(topsecond * topfirst) # If the operator is '*' then perform a multiplication operation # on the top two elements by popping them out. elif charact == '/': givenstack.append(topsecond // topfirst) # The only number in the stack is the final answer when the expression is traversed. # return the answer to the main function return givenstack.pop() # Driver code # Give the postfix Expression as static input and store it in a variable. givenExp = "91-82×63+" # Pass the given postfix Expression as an argument to evalpostfix function print('The value of the given postfix expression =', evaluatePostfix(givenExp))
Output:
The value of the given postfix expression = 9
3)Implementation(User Input)
Approach:
- Give the postfix Expression as user input using the input() function and store it in a variable.
- Pass the given postfix Expression as an argument to evalpostfix function
- Create a stack by taking an empty list which acts as a stack in this case to hold operands (or values).
- Traverse the given postfix expression using For loop.
- Do the following for each scanned element.
a) Push the element into the stack if it is a number.
b) Evaluate the operator and return the answer to the stack. - If the operator is ‘+’ then perform an addition operation on the top two elements by popping them out.
- If the operator is ‘-‘ then perform a subtraction operation on the top two elements by popping them out.
- If the operator is ‘/’ then perform a division operation on the top two elements by popping them out.
- If the operator is ‘*’ then perform a multiplication operation on the top two elements by popping them out.
- The only number in the stack is the final answer when the expression is traversed.
- The Exit of the Program.
Below is the implementation:
# Function which accepts the given postfix expression as argument # and evaluates the expression using stack and return the value def evaluatePostfix(givenExp): # Create a stack by taking an empty list which acts # as a stack in this case to hold operands (or values). givenstack = [] # Traverse the given postfix expression using For loop. for charact in givenExp: # Push the element into the given stack if it is a number. if charact.isdigit(): givenstack.append(int(charact)) # if the character is operator else: # remove the top two elements from the stack topfirst = givenstack.pop() topsecond = givenstack.pop() # Evaluate the operator and return the answer to the stack using append() funtion. # If the operator is '+' then perform an addition operation on # the top two elements by popping them out. if charact == '+': givenstack.append(topsecond + topfirst) # If the operator is '-' then perform a subtraction operation # on the top two elements by popping them out. elif charact == '-': givenstack.append(topsecond - topfirst) # If the operator is '/' then perform a division operation on # the top two elements by popping them out. elif charact == '×': givenstack.append(topsecond * topfirst) # If the operator is '*' then perform a multiplication operation # on the top two elements by popping them out. elif charact == '/': givenstack.append(topsecond // topfirst) # The only number in the stack is the final answer when the expression is traversed. # return the answer to the main function return givenstack.pop() # Driver code # Give the postfix Expression as user input using input() function and store it in a variable. givenExp = input('Enter some random postfix Expression = ') # Pass the given postfix Expression as an argument to evalpostfix function print('The value of the given postfix expression =', evaluatePostfix(givenExp))
Output:
Enter some random postfix Expression = 72/96-8+ The value of the given postfix expression = 11
Related Programs:
- Python Program to Count the Frequency of Words Appearing in a String Using a Dictionary
- Python Program to Print Numbers in a Range (1,upper) Without Using any Loops or by Using Recursion
- Python Program to Check Whether a String is a Palindrome or not Using Recursion
- Python Program to Find if a Number is Prime or Not Prime Using Recursion
- Python Program to Find the Power of a Number Using Recursion
- Python Program to Read Print Prime Numbers in a Range using Sieve of Eratosthenes
- Python Program to Reverse a String Using Recursion