#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
// Stack implementation
typedef struct
{
int data[MAX];
int top;
} Stack;
// Function to initialize the stack
void initStack(Stack *s)
{
s->top = -1;
}
// Function to check if the stack is empty
int isEmpty(Stack *s)
{
return s->top == -1;
}
// Function to push an element into the stack
void push(Stack *s, int value)
{
if (s->top == MAX - 1)
{
printf("Stack Overflow\n");
return;
}
s->data[++(s->top)] = value;
}
// Function to pop an element from the stack
int pop(Stack *s)
{
if (isEmpty(s))
{
printf("Stack Underflow\n");
return -1;
}
return s->data[(s->top)--];
}
// Function to evaluate a prefix expression
int evaluatePrefix(char *exp)
{
Stack s;
initStack(&s);
int i = strlen(exp) - 1;
// Scan the prefix expression from right to left
while (i >= 0)
{
// Skip spaces
if (exp[i] == ' ')
{
i--;
continue;
}
// If the character is an operand (digit)
if (isdigit(exp[i]))
{
int num = 0, base = 1;
// There could be multiple digits, so we build the number
while (i >= 0 && isdigit(exp[i]))
{
num = num + (exp[i] - '0') * base;
base *= 10;
i--;
}
// Push the number onto the stack
push(&s, num);
}
// If the character is an operator
else {
int operand1 = pop(&s);
int operand2 = pop(&s);
switch (exp[i])
{
case '+':
push(&s, operand1 + operand2);
break;
case '-':
push(&s, operand1 - operand2);
break;
case '*':
push(&s, operand1 * operand2);
break;
case '/':
if (operand2 != 0)
push(&s, operand1 / operand2);
else
printf("Division by zero error\n");
break;
default:
printf("Invalid operator\n");
return -1;
}
i--;
}
}
// The result will be the last element in the stack
return pop(&s);
}
int main()
{
char prefixExp[MAX];
printf("Enter a valid prefix expression: ");
fgets(prefixExp, MAX, stdin);
// Evaluate the prefix expression
int result = evaluatePrefix(prefixExp);
printf("The result of the prefix expression is: %d\n", result);
return 0;
}
Explanation
- Prefix Expression: In prefix notation, the operator is placed before its operands. For example, the expression
+ 9 * 2 6is equivalent to(9 + (2 * 6))in infix notation. - Stack Data Structure: We use a stack to evaluate the expression. The key idea is to traverse the expression from right to left, push operands onto the stack, and whenever an operator is encountered, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.
- Digits Handling: Since prefix expressions can contain multi-digit numbers, we handle them by constructing the number digit by digit, starting from the least significant digit.
- Operators: When encountering an operator, we pop two operands from the stack, apply the operator, and push the result back onto the stack.
- Result: Once the entire expression is processed, the result is the only value remaining in the stack.
Sample Input and Output
Enter a valid prefix expression: + 9 * 2 6
The result of the prefix expression is: 21
Here, the expression + 9 * 2 6 translates to 9 + (2 * 6) in infix, which equals 21. The program correctly evaluates this.
How the Program Works:
- The program reads the prefix expression from the user.
- It then processes the expression by pushing operands to the stack and applying operators to the top two operands on the stack.
- Finally, it prints the result of the evaluated prefix expression.
This approach ensures correct evaluation by leveraging the stack data structure to reverse the order of operations as required by the prefix notation.
