Evaluation Of Prefix Expression Using Stack In C
- Expressions with prefixes and suffixes can be evaluated more quickly than those with infixes. This is due to the fact that operator precedence rules and processing of any brackets are not necessary.
- Regardless of its priority, the operator that appears before another in postfix and prefix expressions will be evaluated first. Additionally, these expressions don't have any brackets.
- It can be evaluated correctly as long as we can ensure that a valid prefix or postfix expression is being utilised.
- Both infix to postfix and infix to prefix conversions are possible. However, this procedure is comparable to that of evaluating a prefix expression.
Algorithm To Evaluate the Prefix Expression Using Stack:
EVALUATE_PREFIX_EXPRESSION(STRING)
Step 1: place a pointer P to the end of the end
Step 2: Push the operand-containing character at P to the stack if it is one.
Step 3: Take two elements out of the Stack if the character at position P is an operator. Apply the operator on these elements, and then push the outcome back to the stack.
Step 4: As long as there are still characters in the expression that need to be scanned, move on to Step 2 after decreasing P by 1.
Step 5: The Result is retained at the top of the stack; that has to be returned.
Step 6: End
Below is an example to show how the algorithm works:
Expression: +9*26
Input Character | Stack | Explanation |
6 | 6 | Here 6 is an operand, so push into stack |
2 | 6 2 | Here 2 is an operand, so push into stack |
* | 12 (6*2) | * is an operator hence pop 6 and 2 perform multiplication and push the result into Stack |
9 | 12 9 | Here 9 is an operand, so push into stack |
+ | 21 (12+9) | + is an operator hence pop 12 and 9 perform addition and push the result into Stack |
Hence, the result it has is 21.
C Program to Evaluate the Prefix Expression:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct Stack
{
double data;
struct Stack* next;
};
struct Stack* createStack()
{
return NULL;
}
void push(struct Stack** top, double data)
{
struct Stack* newNode = (struct Stack*)malloc(sizeof(struct Stack));
if (newNode == NULL)
{
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = *top;
*top = newNode;
}
double pop(struct Stack** top)
{
if (*top == NULL)
{
printf("Stack is empty\n");
exit(1);
}
struct Stack* temp = *top;
double data = temp->data;
*top = (*top)->next;
free(temp);
return data;
}
double Evaluate_Prefix_Expression(char* exprsn)
{
struct Stack* Stack = createStack();
int j = strlen(exprsn) - 1;
while (j >= 0)
{
if (exprsn[j] == ' ')
{
j--;
continue;
}
if (isdigit(exprsn[j]))
{
double num = 0, i = j;
while (j >= 0 && isdigit(exprsn[j]))
j--;
j++;
for (int k = j; k <= i; k++)
num = num * 10 + (double)(exprsn[k] - '0');
push(&Stack, num);
}
else
{
double o1 = pop(&Stack);
double o2 = pop(&Stack);
switch (exprsn[j])
{
case '+':
push(&Stack, o1 + o2);
break;
case '-':
push(&Stack, o1 - o2);
break;
case '*':
push(&Stack, o1 * o2);
break;
case '/':
push(&Stack, o1 / o2);
break;
}
}
j--;
}
return pop(&Stack);
}
int main()
{
char exprsn[] = "+ 9 * 12 6";
printf("%lf\n", Evaluate_Prefix_Expression(exprsn));
return 0;
}
OUTPUT:
![Evaluation Of Prefix Expression Using Stack In C](https://static.tutorialandexample.com/c/evaluation-of-prefix-expression-using-stack-in-c1.png)