Evaluation of Postfix Expression using Stack
To evaluate a postfix expression using a stack, we follow these steps:
1. Create an empty stack to store operands.
2. Scan the postfix expression from left to right.
3. If the current character is an operand (a number), push it onto the stack.
4. If the current character is an operator, pop the top two elements from the stack, perform the operation, and push the result back onto the stack.
5. After scanning the entire expression, the final value on the stack is the evaluated result.
Below, we have a C code that shows the evaluation of a postfix expression using a stack:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
void push(int item) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
}
stack[++top] = item;
}
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
int evaluatePostfix(char* exp) {
int i, operand1, operand2, result;
for (i = 0; exp[i] != '\0'; i++) {
if (isdigit(exp[i])) {
push(exp[i] - '0');
}
else {
operand2 = pop();
operand1 = pop();
switch (exp[i]) {
case '+': result = operand1 + operand2; break;
case '-': result = operand1 - operand2; break;
case '*': result = operand1 * operand2; break;
case '/': result = operand1 / operand2; break;
}
push(result);
}
}
return pop();
}
int main() {
char postfix[MAX_SIZE];
printf("Enter a postfix expression: ");
scanf("%s", postfix);
printf("Evaluated result: %d\n", evaluatePostfix(postfix));
return 0;
}
You can also try this code with Online C Compiler
Output
Enter a postfix expression: 523*+
Evaluated result: 11
In this code, we define a stack using an array `stack` and keep track of the top element using the variable `top`. The `push` and `pop` functions are used to push and pop elements from the stack, respectively.
The `evaluatePostfix` function takes a postfix expression as input and evaluates it using the stack. It scans the expression character by character. If the current character is a digit, it is converted to an integer and pushed onto the stack. If the current character is an operator, the top two elements are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
After scanning the entire expression, the final value on the stack is the evaluated result, which is returned by the `evaluatePostfix` function.
In the `main` function, we prompt the user to enter a postfix expression, call the `evaluatePostfix` function to evaluate it and print the result.
Illustration
Let's discuss an example to understand the step-by-step evaluation of a postfix expression using a stack. Consider the postfix expression "5 2 3 * +".
+------------+
| |
| Stack: [] |
| |
+-----+------+
|
v
+------------+
| |
| Stack: [5] |
| |
+-----+------+
|
v
+------------+
| |
| Stack: [5, 2] |
| |
+-----+------+
|
v
+------------+
| |
| Stack: [5, 2, 3] |
| |
+-----+------+
|
v
+------------+
| |
| Stack: [5, 6] |
| |
+-----+------+
|
v
+------------+
| |
| Stack: [11] |
| |
+-----+------+
|
v
+------------+
| |
| Final Result: 11 |
| |
+------------+
Step 1: Create an empty stack.
Stack: []
Step 2: Scan the expression from left to right.
Current character: '5'
Action: Push 5 onto the stack.
Stack: [5]
Step 3: Scan the next character.
Current character: '2'
Action: Push 2 onto the stack.
Stack: [5, 2]
Step 4: Scan the next character.
Current character: '3'
Action: Push 3 onto the stack.
Stack: [5, 2, 3]
Step 5: Scan the next character.
Current character: '*'
Action: Pop the top two elements (3 and 2), multiply them (2 * 3 = 6), and push the result back onto the stack.
Stack: [5, 6]
Step 6: Scan the next character.
Current character: '+'
Action: Pop the top two elements (6 and 5), add them (5 + 6 = 11), and push the result back onto the stack.
Stack: [11]
Step 7: The expression has been fully scanned. The final value on the stack (11) is the evaluated result of the postfix expression.
This step-by-step illustration shows how the stack stores operands and performs operations based on the operators encountered in the postfix expression.
Postfix evaluation for multi-digit numbers
The previous examples and code assume single-digit operands in the postfix expression. However, in real-world scenarios, we often deal with multi-digit numbers. To handle multi-digit numbers, we need to modify the evaluation process slightly.
Let’s take a look at an updated version of the `evaluatePostfix` function that supports multi-digit numbers:
int evaluatePostfix(char* exp) {
int i, operand, operand1, operand2, result;
for (i = 0; exp[i] != '\0'; i++) {
if (isdigit(exp[i])) {
operand = 0;
while (isdigit(exp[i])) {
operand = operand * 10 + (exp[i] - '0');
i++;
}
i--;
push(operand);
}
else if (exp[i] == ' ') {
continue;
}
else {
operand2 = pop();
operand1 = pop();
switch (exp[i]) {
case '+': result = operand1 + operand2; break;
case '-': result = operand1 - operand2; break;
case '*': result = operand1 * operand2; break;
case '/': result = operand1 / operand2; break;
}
push(result);
}
}
return pop();
}
In this updated version, when we encounter a digit, we extract the complete multi-digit number by continuously multiplying the previous operand by 10 and adding the current digit until a non-digit character is encountered. We also skip any whitespace characters.
For example, if the postfix expression is "23 45 * 6 +", the evaluation process would be like:
1. Push 23 onto the stack: [23]
2. Push 45 onto the stack: [23, 45]
3. Encounter '*', pop 45 and 23, multiply them (23 * 45 = 1035), and push the result: [1035]
4. Push 6 onto the stack: [1035, 6]
5. Encounter '+', pop 6 and 1035, add them (1035 + 6 = 1041), and push the result: [1041]
The final result is 1041, which is the evaluated value of the postfix expression "23 45 * 6 +".
With this modification, the postfix evaluation code can handle multi-digit numbers in the expression.
Frequently Asked Questions
Can the postfix evaluation algorithm handle decimal numbers?
No, the current implementation only supports integer operands. To handle decimal numbers, you would need to modify the code to use floating-point data types.
Is it possible to evaluate expressions with parentheses using this algorithm?
No, the postfix notation eliminates the need for parentheses. If you have an expression with parentheses, you should first convert it to postfix notation before evaluation.
Can the postfix evaluation algorithm be extended to support additional operators?
Yes, you can extend the algorithm to support more operators by adding additional cases in the switch statement and implementing the corresponding operations.
Conclusion
In this article, we discussed evaluating postfix expressions using a stack in C. We covered the basic algorithm, provided code examples, and explained the evaluation process step by step. We also discussed how to handle multi-digit numbers in postfix expressions.
You can also check out our other blogs on Code360.
245+ registered 
