.png)
In this blog, you will learn to convert infix to postfix using C.
Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
Why postfix representation of expression? Because the compiler scans the expression either from left to right or from right to left.
Consider the expression:
a op b op1 c op2 d
if op = +, op1 = *, op2 = +The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.
The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation.
The subsequent expression in the postfix form is abc*+d+. The postfix expressions can be evaluated easily using a stack.
Infix to Postfix Conversion
Let Q be an infix expression and we have to convert it to postfix expression P. For this the following procedure will be followed.
1. Push left parenthesis onto STACK and add right parenthesis at the end of Q.
2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty.
3. If an operand is encountered add it to P.
4. If a left parenthesis is encountered push it onto the STACK.
5. If an operator is encountered, then
Repeatedly pop from STACK and add to P each operator which has the same precedence as or higher precedence than the operator encountered.
Push the encountered operator onto the STACK.
6. If a right parenthesis is encountered, then
Repeatedly pop from the STACK and add to P each operator until a left parenthesis is encountered.
Remove the left parenthesis; do not add it to P.
7. Exit
Implementation:
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;
int precedence(char);
void init(stack *);
void push(stack *,int);
int pop(stack *);
int empty(stack *);
int full(stack *);
int top(stack *); //value of the top element
void infix_to_postfix(char infix[],char postfix[]);
void main()
{
char infix[30],postfix[30];
printf("Enter an infix expression(eg: 5+2*4): ");
gets(infix);
infix_to_postfix(infix,postfix);
printf("\n Postfix expression: %s",postfix);
}
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
char x,token;
int i,j; //i-index of infix,j-index of postfix
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token=='(')
push(&s,'(');
else
if(token==')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s))&&!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}
int precedence(char x)
{
if(x=='(')
return(0);
if(x=='+'||x=='-')
return(1);
if(x=='*'||x=='/'||x=='%')
return(2);
return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1)
return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1)
return(1);
return(0);
}
void push(stack *s,int x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack *p)
{
return (p->data[p->top]);
}Output:
Enter an infix expression(eg: 5+2*4): a*(b+c)/d+g
Postfix expression: abc+*d/g+Problems on Stack
#1: Print Reverse of linked list using Stack
We are given a linked list. We have to print the reverse of the linked list using Stack.
[10 20 30 40 50]
[50 40 30 20 10]Solution:
We will traverse the linked list and push all the nodes of the linked list to the stack. Since stack has the property of Last In, First Out, List is automatically reversed when we will pop the stack elements one by one.
Algorithm:
void printreverse(Node *head)
{
stack < Node* > stk
current = head
while(current != NULL)
{
stk.push(current)
current = current->next
}
while(!stk.empty())
{
node = stk.top()
print(node->data)
stk.pop()
}
}Time Complexity: O(n)
Auxiliary Space: O(n)
#2: Check for balanced parentheses in an expression
Given an expression string exp, we have to check whether the pairs and the orders of { “, ” }, ( “, ” ) and [ “, ” ] are correct in exp. For example -
Input : [ ( ) ] { } { [ ( ) ( ) ] ( ) }
Output : true
Input : { [ ( ] ) }
Output : falseSolution:
1) Declare a character stack stk.
2) Now traverse the expression string exp.
If the current character is a starting bracket ‘(‘ or ‘{‘ or ‘[‘ then push it to stack.
If the current character is a closing bracket ‘)’ or ‘}’ or ‘]’ then pop from the stack and if the popped character is the matching starting bracket then fine else parenthesis is not balanced.
3) After complete traversal, if there is some starting bracket left in the stack then “not balanced”.
Algorithm:
bool isBalanced(string expr)
{
stack < char > stk
for i=0 to expr.size() {
if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
stk.push(expr[i])
continue
}
if stk.empty()
return false
switch (expr[i]) {
case ')': {
x = stk.top()
stk.pop()
if (x=='{' || x=='[')
return false
break
}
case '}': {
x = stk.top();
stk.pop();
if (x=='(' || x=='[')
return false
break
}
case ']': {
x = stk.top();
stk.pop();
if (x =='(' || x == '{')
return false
break
}
}
}
return (stk.empty())
} Time Complexity: O(n)
Auxiliary Space: O(n)
#3: Next Greater Element
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1.
Input: [5, 2, 6, 12]
Output:
Element NGE
5 --> 6
2 --> 5
6 --> 12
12 --> -1Solution:
1) Push the first element to stack.
2) Pick the rest of the elements one by one and follow the following steps in the loop.
Mark the current element as next.
If the stack is not empty, compare the top element of the stack with next.
If next is greater than the top element, the Pop element from the stack. next is the next greater element for the popped element.
Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
Finally, push the next in the stack.
3) After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.
Algorithm:
void printNGE(arr, n)
{
stack < int > stk
stk.push(arr[0])
for i=0 to n-1 {
if (stk.empty()) {
stk.push(arr[i])
continue
}
while (stk.empty() == false && stk.top() < arr[i]) {
print(stk.top() + "-->" + arr[i])
stk.pop()
}
stk.push(arr[i])
while (stk.empty() == false) {
print(stk.top() + "-->" + -1)
stk.pop()
}
}
}Time Complexity :O(n)
Auxiliary Space :O(n)
Happy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.
Comments