[go: up one dir, main page]
Scribd
Upload
254 views7 pages

Evaluation of Postfix Expressions

Uploaded by

Jhanvikuvarba Solanki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
254 views7 pages

Evaluation of Postfix Expressions

Uploaded by

Jhanvikuvarba Solanki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Evaluation of Postfix Expressions

Postfix notation, also known as Reverse Polish Notation (RPN), is a


mathematical notation in which every operator follows all of its operands.
The evaluation of postfix expressions is straightforward and can be
efficiently implemented using a stack. Here’s how it works:
Steps to Evaluate a Postfix Expression:
1. Initialize an Empty Stack:
o Start with an empty stack to hold operands.
2. Read the Postfix Expression from Left to Right:
o Traverse the postfix expression one symbol at a time.
3. For Each Symbol in the Expression:
o Operand:
▪ If the symbol is an operand (e.g., a number or a variable),
push it onto the stack.
o Operator:
▪ If the symbol is an operator (e.g., +, -, *, /, ^), pop the
required number of operands from the stack (two for
binary operators), perform the operation, and push the
result back onto the stack.
4. Repeat the Process:
o Continue the process until you have processed all symbols in the
postfix expression.
5. Final Result:
o After the entire expression has been processed, the final result
will be the only item remaining in the stack. Pop this value, which
is the result of the postfix expression.

Example:
Let's evaluate the postfix expression:
562-32^*4/+
Step-by-Step Evaluation:
Step Symbol Stack Action

1 5 [5] Push 5 onto the stack.

2 6 [5, 6] Push 6 onto the stack.

3 2 [5, 6, 2] Push 2 onto the stack.

Pop 6 and 2, compute 6 - 2 = 4, push 4 onto the


4 - [5, 4]
stack.

5 3 [5, 4, 3] Push 3 onto the stack.

[5, 4, 3,
6 2 Push 2 onto the stack.
2]

Pop 3 and 2, compute 3 ^ 2 = 9, push 9 onto the


7 ^ [5, 4, 9]
stack.

Pop 4 and 9, compute 4 * 9 = 36, push 36 onto the


8 * [5, 36]
stack.

9 4 [5, 36, 4] Push 4 onto the stack.

Pop 36 and 4, compute 36 / 4 = 9, push 9 onto the


10 / [5, 9]
stack.

Pop 5 and 9, compute 5 + 9 = 14, push 14 onto the


11 + [14]
stack.
Final Result:
• After evaluating the entire postfix expression, the only item left in the
stack is 14.
• Result: The value of the postfix expression 5 6 2 - 3 2 ^ * 4 / + is 14.
Key Points:
• Stack Usage: The stack is used to temporarily hold operands until they
are needed for an operation. After the operation, the result is pushed
back onto the stack for future use.
• Efficiency: Postfix evaluation is efficient because it avoids the need for
parentheses and respects the operator precedence inherently, making
it easier to compute the result.
• Application: This method is widely used in computer systems,
particularly in calculators, compilers, and interpreters, where it is
necessary to evaluate mathematical expressions quickly and
accurately.

Algorithm to Evaluate a Postfix Expression


Here's a step-by-step algorithm to evaluate a postfix expression using a
stack:

1. Initialize an empty stack S to store operands.


2. Read the postfix expression from left to right.
3. For each symbol ch in the postfix expression:
a. If ch is an operand (e.g., a number or a variable):
o Push ch onto stack S.
b. If ch is an operator (e.g., +, -, *, /, ^):
o Pop the top two elements from the stack:
▪ Let operand2 = S.pop()
▪ Let operand1 = S.pop()
o Perform the operation ch with operand1 and operand2:
▪ Compute result = operand1 ch operand2
o Push the result of the operation back onto stack S.
4. After processing all symbols in the postfix expression:
o The final result of the postfix expression will be the only element
left in the stack.
5. Return the result by popping the last element from the stack: result =
S.pop().
Example 1:
Postfix Expression:
78+32*-
Step-by-Step Evaluation:
1. Input: Postfix Expression = 7 8 + 3 2 * -
2. Initialize: Stack S = []
3. Process each symbol:
o 7 is an operand → Push onto stack → S = [7]
o 8 is an operand → Push onto stack → S = [7, 8]
o + is an operator → Pop 8 and 7, compute 7 + 8 = 15, push result
→ S = [15]
o 3 is an operand → Push onto stack → S = [15, 3]
o 2 is an operand → Push onto stack → S = [15, 3, 2]
o * is an operator → Pop 2 and 3, compute 3 * 2 = 6, push result →
S = [15, 6]
o - is an operator → Pop 6 and 15, compute 15 - 6 = 9, push result
→ S = [9]
4. Final Stack: S = [9]
o The final result of the postfix expression is 9.

Example 2:
Postfix Expression:
4572+*-3/
Step-by-Step Evaluation:
1. Input: Postfix Expression = 4 5 7 2 + * - 3 /
2. Initialize: Stack S = []
3. Process each symbol:
o 4 is an operand → Push onto stack → S = [4]
o 5 is an operand → Push onto stack → S = [4, 5]
o 7 is an operand → Push onto stack → S = [4, 5, 7]
o 2 is an operand → Push onto stack → S = [4, 5, 7, 2]
o + is an operator → Pop 2 and 7, compute 7 + 2 = 9, push result →
S = [4, 5, 9]
o * is an operator → Pop 9 and 5, compute 5 * 9 = 45, push result
→ S = [4, 45]
o - is an operator → Pop 45 and 4, compute 4 - 45 = -41, push result
→ S = [-41]
o 3 is an operand → Push onto stack → S = [-41, 3]
o / is an operator → Pop 3 and -41, compute -41 / 3 ≈ -13.67, push
result → S = [-13.67]
4. Final Stack: S = [-13.67]
o The final result of the postfix expression is approximately -13.67.

Example 3:
Postfix Expression:
10 2 8 * + 3 -
Step-by-Step Evaluation:
1. Input: Postfix Expression = 10 2 8 * + 3 -
2. Initialize: Stack S = []
3. Process each symbol:
o 10 is an operand → Push onto stack → S = [10]
o 2 is an operand → Push onto stack → S = [10, 2]
o 8 is an operand → Push onto stack → S = [10, 2, 8]
o * is an operator → Pop 8 and 2, compute 2 * 8 = 16, push result
→ S = [10, 16]
o + is an operator → Pop 16 and 10, compute 10 + 16 = 26, push
result → S = [26]
o 3 is an operand → Push onto stack → S = [26, 3]
o - is an operator → Pop 3 and 26, compute 26 - 3 = 23, push result
→ S = [23]
4. Final Stack: S = [23]
o The final result of the postfix expression is 23.

Example 4:
Postfix Expression:
234*+56*-
Step-by-Step Evaluation:
1. Input: Postfix Expression = 2 3 4 * + 5 6 * -
2. Initialize: Stack S = []
3. Process each symbol:
o 2 is an operand → Push onto stack → S = [2]
o 3 is an operand → Push onto stack → S = [2, 3]
o 4 is an operand → Push onto stack → S = [2, 3, 4]
o * is an operator → Pop 4 and 3, compute 3 * 4 = 12, push result
→ S = [2, 12]
o + is an operator → Pop 12 and 2, compute 2 + 12 = 14, push result
→ S = [14]
o 5 is an operand → Push onto stack → S = [14, 5]
o 6 is an operand → Push onto stack → S = [14, 5, 6]
o * is an operator → Pop 6 and 5, compute 5 * 6 = 30, push result
→ S = [14, 30]
o - is an operator → Pop 30 and 14, compute 14 - 30 = -16, push
result → S = [-16]
4. Final Stack: S = [-16]
o The final result of the postfix expression is -16.

You might also like