Postfix using ‘C’

In computer science and mathematics, postfix notation, also known as reverse Polish notation (RPN), is a way to represent mathematical expressions without using parentheses to indicate the order of operations. In postfix notation, the operator is written after its operands.

Here's an example to illustrate the conversion from infix notation to postfix notation:

Infix notation: 2 + 3 * 4 Postfix notation: 2 3 4 * +

To evaluate an expression in postfix notation, you can use a stack-based algorithm. Here's how it works:

1.    Initialize an empty stack.

2.    Scan the expression from left to right.

3.    For each token (operand or operator) in the expression:

·        If the token is an operand, push it onto the stack.

·        If the token is an operator, pop the top two operands from the stack.

·        The first popped operand becomes the second operand in the operation.

·        The second popped operand becomes the first operand in the operation.

·        Perform the operation using the operator and the operands.

·        Push the result back onto the stack.

4.    After scanning all tokens, the final result will be the only value left on the stack.

Using the previous postfix expression as an example:

Postfix notation: 2 3 4 * + Evaluation:

  • Push 2 onto the stack.
  • Push 3 onto the stack.
  • Push 4 onto the stack.
  • Pop 4 and 3 from the stack. Perform the multiplication (4 * 3 = 12). Push 12 onto the stack.
  • Pop 12 and 2 from the stack. Perform the addition (12 + 2 = 14). Push 14 onto the stack.
  • The final result is 14.

So, the expression "2 + 3 * 4" in infix notation evaluates to 14 in postfix notation.

Postfix notation is often used in calculators and stack-based virtual machines because it eliminates the need for parentheses and allows for straightforward evaluation using a stack.

Note: When converting from infix to postfix, it's important to follow the precedence rules of the operators. For example, multiplication has higher precedence than addition, so it is performed before addition in the postfix expression. If needed, parentheses can be used in the infix expression to enforce a specific order of operations.

Program:-

#include<stdio.h>

#include<string.h>

int priority(int ch)

{

if(ch=='+'||ch=='-')

{

return 1;

}

if(ch=='*'||ch=='/')

{

return 2;

}

if(ch=='^')

{

return 3;

}

else

{

return 0;

}

}

void main()

{

char p[100],in[100],ch,c,s[100];

int i,k=0,top=-1;

printf("enter infix expression");

scanf("%s",in);

s[++top]='(';

strcat(in,")");

for(i=0;in[i]!='\0';i++)

{

ch=in[i];

if(isalnum(ch))

p[k++]=ch;

else if(ch=='(')

s[++top]=ch;

else if(ch==')')

{

c=s[top--];

while(c!='('){

p[k++]=c;

c=s[top--];

}

}

else

{

while(priority(ch)<=priority(s[top])&&top!=-1)

{

p[k++]=s[top--];

 

}

s[++top]=ch;

}

}

p[k]='\0';

printf("\npostfix expression %s",p);

}

Output:-