Data Structures - Infix to Postfix Conversion - Cpp

In this post we convert an infix expression to postfix expression using stack data structure .

Generally an infix expression is a normal expression where operators are present in between the operands ex : A + B * C and  its postfix  notation is represented as ABC*+

An infix expression is converted into its postfix notation as follows : Create an empty Stack for pushing and poping operators and a string for storing result First scan the infix exppression from left to right if there is no exponential operator , if there is an exponential operator scan the infix expression from right to left. If an operand is encountered add it to the result string If a left parenthesis is encountered push it to the stack If a right parenthesis is encountered pop the stack until its corresponding left parenthesis is removed and append each operator to the result string   If an operator is encountered push it to the stack if the encountered operator is of lower precedence that the stack top element and pop all elements with higher or equal precedence and add to result string. Check if there are any elements in the stack and pop them out and add to the result string.

Download code

PROGRAM :

    #include<iostream>
    #include<stack>
    #include<string>

    using namespace std;
    string InfixToPostfix(string expression);
    int HasHigherPrecedence(char operator1, char operator2);
    bool IsOperator(char C);
    bool IsOperand(char C);

    int main()
    {
        string expression;
        cout<<"Enter Infix Expression: \t";
        getline(cin,expression);
        string postfix = InfixToPostfix(expression);
        cout<<"Postfix expression = \t"<<postfix<<"\n";
        return 0;
    }
    string InfixToPostfix(string expression)
    {

        stack<char> S;
        string postfix = "";
        for(int i = 0; i< expression.length(); i++)
        {
        if(expression[i] == ' ' || expression[i] == ',')
            continue;
        else if(IsOperator(expression[i]))
        {
            while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
            {
                postfix+= S.top();
                S.pop();
            }
            S.push(expression[i]);
        }
        else if(IsOperand(expression[i]))
        {
            postfix +=expression[i];
        }

        else if (expression[i] == '(')
        {
            S.push(expression[i]);
        }

        else if(expression[i] == ')')
        {
            while(!S.empty() && S.top() !=  '(')
            {
                postfix += S.top();
                S.pop();
            }
            S.pop();
        }
        }

        while(!S.empty())
        {
        postfix += S.top();
        S.pop();
        }

        return postfix;
    }
    bool IsOperand(char C)
    {
        if(C >= '0' && C <= '9') return true;
        if(C >= 'a' && C <= 'z') return true;
        if(C >= 'A' && C <= 'Z') return true;
        return false;
    }
    bool IsOperator(char C)
    {
        if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^')
        return true;
        return false;
    }
    int IsRightAssociative(char op)
    {
        if(op == '^')
        return true;
        return false;
    }
    bool IsLeftParenthesis(char ch)
    {
        if (ch == '(')
        return true;
        return false;
    }
    bool IsRightParenthesis(char ch)
    {
        if (ch == ')')
        return true;
        return false;
    }
    int GetOperatorWeight(char op)
    {
        int weight = -1;
        switch(op)
        {
        case '+':
        case '-':
        weight = 1;
        break;
        case '*':
        case '/':
        weight = 2;
        break;
        case '^':
        weight = 3;
        break;
        }
        return weight;
    }
    int HasHigherPrecedence(char op1, char op2)
    {
        int op1Weight = GetOperatorWeight(op1);
        int op2Weight = GetOperatorWeight(op2);
        if(op1Weight == op2Weight)
        {
        if(IsRightAssociative(op1))
            return false;
        else
            return true;
        }
        return op1Weight > op2Weight ?  true: false;
    }

Download code

OUTPUT :

Cpp - Data Structures - Infix to Postfix 

Cpp - Data Structures - Infix to Postfix 

Cpp - Data Structures - Infix to Postfix 

Data Structures - Cpp Program to implement stack operations

In this post we will see some basic operations of stack like insertion , deletion . Generally a stack is a an abstract data type where insertion and deletion takes place at one end and that end is know as top. Inserting an item to stack is called as PUSH operation. Removing an item from a stack is called as POP operation. Inserting or deleting an item takes place at one end and they are done one by one.

See the image below

"Data stack" by User:Boivie - made in Inkscape, by myself User:Boivie. Based on Image:Stack-sv.png, originally uploaded to the Swedish Wikipedia in 2004 by sv:User:Shrimp. Licensed under Public Domain via Wikimedia Commons.

The principle of the stack is : Last In First Out (LIFO)
Here in this program we initially take top as -1 and when an element is inserted top is incremented and pushes the value in stack , similarly when when an element is deleted top is decremented and pops the value from stack.

There are two error conditions here :

1. Stack Overflow
2. Stack Underflow

Stack Overflow is a situation where the stack is full and we still trying to insert elements to that stack.
Stack Underflow is a situation where the stack is empty and we are still trying to delete  elements from that stack.

PROGRAM : 

#include <iostream>
#define MAX 10
using namespace std;
void push(int);
int pop();
int top = -1;
int stack[MAX];
int main()
{
    int element,choice,d;

    while(1)
    {
        cout << "\nSTACK OPERATIONS \n\n";
        cout << "1.Insert \n";
        cout << "2.Delete \n";
        cout << "3.Display \n";
        cout << "4.Exit\n\n";
        cout << "Enter your choice. \t";
        cin >> choice;

        switch (choice)
        {
        case 1:
            if ( top == MAX - 1 )
                cout << "\nSTACK is already full. Delete some elements and try again ! \n ERROR : STACK OVERFLOW\n";
            else
            {
                cout << "\nEnter the value to insert.\t";
                cin >> element;
                push(element);
            }
            break;
        case 2:
            if ( top == -1 )
                cout << "\nSTACK is already empty. \n ERROR : STACK UNDERFLOW\n";
            else
            {
                element = pop();
                cout << "Element removed from stack is "<<  element<< endl;
            }
            break;
        case 3:
            if ( top == -1 )
                cout << "\nSTACK is empty. Cannot display anything\n";
            else
            {
                cout << "There are"<< (top+1)<<"elements in stack.\n";

                for ( d = top ; d >= 0 ; d-- )
                    cout <<  stack[d] << endl;

            }
            break;
        case 4:
            return 0;
        }
    }
    return 0;
}
void push(int value)
{
    top++;
    stack[top] = value;
}
int pop()
{
    int element;
    if ( top == -1 )
        return top;

    element = stack[top];
    top--;

    return element;
}

OUTPUT : 

Cpp - Stack Operations

Cpp - Stack Operations

Cpp - Stack Operations

Cpp - Stack Operations

Data Structures - Java Program to implement stack operations

In this post we will see some basic operations of stack like insertion , deletion . Generally a stack is a an abstract data type where insertion and deletion takes place at one end and that end is know as top. Inserting an item to stack is called as PUSH operation. Removing an item from a stack is called as POP operation. Inserting or deleting an item takes place at one end and they are done one by one.

See the image below,

"Data stack" by User:Boivie - made in Inkscape, by myself User:Boivie. Based on Image:Stack-sv.png, originally uploaded to the Swedish Wikipedia in 2004 by sv:User:Shrimp. Licensed under Public Domain via Wikimedia Commons.

The principle of the stack is : Last In First Out (LIFO)
Here in this program we initially take top as -1 and when an element is inserted top is incremented and pushes the value in stack , similarly when when an element is deleted top is decremented and pops the value from stack.

There are two error conditions here :

1. Stack Overflow
2. Stack Underflow

Stack Overflow is a situation where the stack is full and we still trying to insert elements to that stack.
Stack Underflow is a situation where the stack is empty and we are still trying to delete  elements from that stack.

PROGRAM :

package codingcorner.in;

import java.util.Scanner;

public class StackOperations {
 static final int MAX = 10;
 static int top = -1;
 static int stack[] = new int[MAX];

 public static void main(String[] args) {
  int element, choice, d;
  Scanner scan = new Scanner(System.in);

  while (true) {
   System.out.print("\nSTACK OPERATIONS \n\n");
   System.out.print("1.Insert \n");
   System.out.print("2.Delete \n");
   System.out.print("3.Display \n");
   System.out.print("4.Exit\n\n");
   System.out.print("Enter your choice. \t");
   choice = scan.nextInt();

   switch (choice) {
   case 1:
    if (top == MAX - 1)
     System.out
       .print("\nSTACK is already full. Delete some elements and try again ! \n ERROR : STACK OVERFLOW\n");
    else {
     System.out.print("\nEnter the value to insert.\t");
     element = scan.nextInt();
     push(element);
    }
    break;
   case 2:
    if (top == -1)
     System.out
       .print("\nSTACK is already empty. \n ERROR : STACK UNDERFLOW\n");
    else {
     element = pop();
     System.out.println("Element removed from stack is "+ element);
    }
    break;
   case 3:
    if (top == -1)
     System.out
       .print("\nSTACK is empty. Cannot display anything\n");
    else {
     System.out.println("There are " + (top + 1)+ " elements in stack.");

     for (d = top; d >= 0; d--)
      System.out.println(stack[d]);
     System.out.print("\n");
    }
    break;
   case 4:
    return;
   }

  }
 }

 private static int pop() {
  int element;
  if (top == -1)
   return top;

  element = stack[top];
  top--;

  return element;
 }

 private static void push(int value) {
  top++;
  stack[top] = value;

 }
}

OUTPUT : 

Java - Stack Operations

Java - Stack Operations

Java - Stack Operations

Java - Stack Operations

Data Structures - C Program to implement stack operations

In this post we will see some basic operations of stack like insertion , deletion . Generally a stack is a an abstract data type where insertion and deletion takes place at one end and that end is know as top. Inserting an item to stack is called as PUSH operation. Removing an item from a stack is called as POP operation. Inserting or deleting an item takes place at one end and they are done one by one.

See the image below,

"Data stack" by User:Boivie - made in Inkscape, by myself User:Boivie. Based on Image:Stack-sv.png, originally uploaded to the Swedish Wikipedia in 2004 by sv:User:Shrimp. Licensed under Public Domain via Wikimedia Commons.

The principle of the stack is : Last In First Out (LIFO)
Here in this program we initially take top as -1 and when an element is inserted top is incremented and pushes the value in stack , similarly when when an element is deleted top is decremented and pops the value from stack.

There are two error conditions here :

1. Stack Overflow
2. Stack Underflow

Stack Overflow is a situation where the stack is full and we still trying to insert elements to that stack.
Stack Underflow is a situation where the stack is empty and we are still trying to delete  elements from that stack.

PROGRAM :

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

void push();
int pop();
int top = -1;
int stack[MAX];
int main()
{
    int element,choice,d;
    
    while(1)
    {
        printf("\nSTACK OPERATIONS \n\n");
        printf("1.Insert \n");
        printf("2.Delete \n");
        printf("3.Display \n");
        printf("4.Exit\n\n");
        printf("Enter your choice. \t");
        scanf("%d",&choice);
        
        switch (choice)
        {
            case 1:
            if ( top == MAX - 1 )
                printf("\nSTACK is already full. Delete some elements and try again ! \n ERROR : STACK OVERFLOW\n");
            else
            {
                printf("\nEnter the value to insert.\t");
                scanf("%d",&element);
                push(element);
            }
            break ;
            case 2:
            if ( top == -1 )
                printf("\nSTACK is already empty. \n ERROR : STACK UNDERFLOW\n");
            else
            {
                element = pop();
                printf("Element removed from stack is %d.\n", element);
            }
            break;
            case 3:
            if ( top == -1 )
                printf("\nSTACK is empty. Cannot display anything\n");
            else
            {
                printf("There are %d elements in stack.\n", top+1);
                
                for ( d = top ; d >= 0 ; d-- )
                    printf("%d\n", stack[d]);
                printf("\n");
            }
            break;
            case 4:
            exit(0);
        }
    }
    return 0;
}
void push(int value)
{
    top++;
    stack[top] = value;
}
int pop()
{
    int element;
    if ( top == -1 )
        return top;
    
    element = stack[top];
    top--;
    
    return element;
}

OUTPUT :