The Infix, Postfix and Prefix

The Infix, Postfix, and Prefix

Infix, Postfix, and Prefix notations are three different but equivalent ways of writing expressions.

Infix notation

Operators are written in the middle of their operands. This is the standard way in which we write expressions. Infix notation needs additional information to make the order of assessment of the operators clear: rules incorporated with the language about operator priority and associativity, and brackets ( ) to permit users to override these rules. An example of infix notation is: A+B

Postfix notation

Operators are written after their operands. The order of evaluation of operators is always left-to-right, and brackets can't be utilized to change this order. Operators act on values immediately to the left of them.This is also known as polish notation. An example of postfix expression is: AB+

Prefix notation

Operators are written before their operands.In spite of the fact that Prefix "operators are assessed left-to-right", they utilize values on their right side, and if these qualities themselves include calculations then this changes the order that the operators must be assessed in. An example for prefix operation is: +AB

Evaluating the postfix operation

In ordinary algebra, we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows:

• Scan the Postfix string from left to right.
• Initialise an empty stack.
• If the scanned character is an operand, add it to the stack. If the scanned character is an operator, there will be at least two operands in the stack.
• If the scanned character is an Operator, then we store the topmost component of the stack(topStack) in a variable 'temp'. Pop the stack. Now, evaluate topStack(Operator)temp. Let the result of this operation be 'retVal'. Pop the stack and Push retVal into the stack.
• Repeat this step till all the characters are scanned.
• After all the characters are scanned, we will have one and only component in the stack. Return topStack (Postfix Evaluation, n.d.).

An example is shown below.

Program to evaluate postfix expression

This program evaluates a postfix expression with the help of stacks. There are two functions in this program: "pushstack" to insert an element to stack and "calculator" to calculate the expression. The postfix expression is given by the user and put onto the stack. It is then evaluated and printed on compiler screen (DS Program to evaluate a postfix expression using stack, n.d.).

The code is given below:

#include

#include

#include

#define MAX 50

int stack[MAX];

char post[MAX];

int top=-1;

void pushstack(int tmp);

void calculator(char c);

void main()

{

int i;

printf("Insert a postfix notation :: ");

gets(post);

for(i=0;i<strlen(post);i++)

{

if(post[i]>='0' && post[i]<='9')

{

pushstack(i);

}

if(post[i]=='+' || post[i]=='-' || post[i]=='*' ||

post[i]=='/' || post[i]=='^')

{

calculator(post[i]);

}

}

printf("\n\nResult :: %d",stack[top]);

getch();

}

void pushstack(int tmp)

{

top++;

stack[top]=(int)(post[tmp]-48);

}

void calculator(char c)

{

int a,b,ans;

a=stack[top];

stack[top]='\0';

top--;

b=stack[top];

stack[top]='\0';

top--;

switch(c)

{

case '+':

ans=b+a;

break;

case '-':

ans=b-a;

break;

case '*':

ans=b*a;

break;

case '/':

ans=b/a;

break;

case '^':

ans=b^a;

break;

default:

ans=0;

}

top++;

stack[top]=ans;

}

We obtain the output as:

Limitations of the program

Although this program evaluates the postfix expressions, it has some limitations as well. This program does nothing in terms of error detection and recovery. Sometimes, the user may input an invalid postfix expression. The user may enter more operands than required. Also, the user may insert negative numbers thinking that it processes negative number as well but the program assumes the minus sign as the subtraction operator. Depending on the nature of the error, the program may come to a halt or give the erroneous results.

Conversion from infix to postfix

Algorithm

• Print operands as they arrive.
• If the stack is void or contains a left bracket on top, push the incoming operator onto the stack.
• If the incoming symbol is a left bracket, push it on the stack.
• If the incoming symbol is a right bracket, pop the stack and print the operators until you see a left bracket. Dispose of the pair of brackets.
• If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
• If the incoming symbol has the same precedence with the top of the stack, use association. If the affiliation is left to right, pop and print the top of the stack and afterward push the incoming operator. If the association is from right to left, push the incoming operator.
• If the incoming symbol lower precedence than the symbol on the top of the stack, pop the stack and print the operator on top of the stack. At that point, test the incoming operator against the new top of the stack.
• At the end of the expression, pop and print all the operators on the stack.

C Code

#include

#include

#include

int precedence(char);

int main()

{

int i,otop=-1,ptop=-1,L1,L;

char infix[100],poststack[100],opstack[100];

puts("enter infix expression:");

gets(infix);

L=strlen(infix);

L1=0;

for(i=0;i<L;i++)

{

if(infix[i]=='(')

{

opstack[++otop]=infix[i];

L1++;

}

else

if(isalpha(infix[i]))

{

poststack[++ptop]=infix[i];

}

else if(infix[i]==')')

{

L1++;

while(opstack[otop]!='(')

{

poststack[++ptop]=opstack[otop--];

}

otop--;

}

else

{

while(precedence(opstack[otop])>=precedence(infix[i]))

{

poststack[++ptop]=opstack[otop--];

}

opstack[++otop]=infix[i];

}

}

while(otop!=-1)

{

poststack[++ptop]=opstack[otop];

otop--;

}

printf("Result: ");

for(i=0;i<L-L1;i++)

{

printf("%c",poststack[i]);

}

getch();

}

int precedence(char c)

{

switch(c)

{

case '$':return 4;

case '*':

case '/':return 3;

case '+':

case '-':return 2;

default:return 1;

}

}

References

DS Program to evaluate a postfix expression using stack. (n.d.). Retrieved from Cprogrambank: http://www.cprogrambank.com/dsprogst4

Postfix Evaluation. (n.d.). Retrieved from Scriptasylum: http://scriptasylum.com/tutorials/infix_postfix/algorithms/postfix-evaluation/