Evaluation of Prefix Expression:
- Prefix and Postfix expressions can be evaluated faster than infix expressions.
- No need to process any brackets or follow operator precedence rule.
- In Postfix or Prefix expressions, which ever the operator comes before will be evaluated first irrespective to priority.
- These expressions not having brackets to evaluate.
Algorithm: To Evaluate Prefix(String)
- Put a pointer ‘p’ at the end of String(come in backward direction)
- If character at ‘p’ is an operand, push it on to Stack.
- If the character at ‘p’ is an operator, POP two elements from the Stack. Operate these elements according to the operator, and PUSH result back to Stack.
- Decrement ‘p’ by 1 and go to step 2 as long as there are characters left in the expression.
- The RESULT is stored at the top of the Stack, return it.
- End.
| #include<stdio.h> #include<string.h> int isOperand(char); int evaluate(char[]); void push(int); int pop(); int stack[20]; int top=-1; int main(){ char pre[20]; int res; printf(“Enter Prefix expression : “); gets(pre); printf(“Input expression : %s \n”, pre); res = evaluate(pre); printf(“Result is : %d \n”, res); return 0; } int evaluate(char exp[]){ int j; for(j=strlen(exp)-1 ; j>=0 ; j–){ if(isOperand(exp[j])){ push(exp[j]-‘0’); } else{ int x,y; x = pop(); y = pop(); switch(exp[j]) { case ‘+’ : push(x+y); break; case ‘-‘ : push(x-y); break; case ‘*’ : push(x*y); break; case ‘/’ : push(x/y); break; } } } return pop(); } int isOperand(char ch) { if(ch>=48 && ch<=57) return 1; else return 0; } void push(int val) { stack[++top] = val; } int pop() { return stack[top–]; } |