DSA using Java - Parsing Expressions

Ordinary airthmetic expressions pke 2*(3*4) are easier for human mind to parse but for an algorithm it would be pretty difficult to parse such an expression. To ease this difficulty, an airthmetic expression can be parsed by an algorithm using a two step approach.

Transform the provided arithmetic expression to postfix notation.

Evaluate the postfix notation.

Infix Notation

Normal airthmetic expression follows Infix Notation in which operator is in between the operands. For example A+B here A is first operand, B is second operand and + is the operator acting on the two operands.

Postfix Notation

Postfix notation varies from normal arithmetic expression or infix notation in a way that the operator follows the operands. For example, consider the following examples

Infix to PostFix Conversion

Before looking into the way to translate Infix to postfix notation, we need to consider following basics of infix expression evaluation.

Evaluation of the infix expression starts from left to right.

Keep precedence in mind, for example * has higher precedence over +. For example

2+3*4 = 2+12.

2+3*4 = 14.

Override precedence using brackets, For example

(2+3)*4 = 5*4.

(2+3)*4= 20.

Now let us transform a simple infix expression A+B*C into a postfix expression manually.

Now let us transform the above infix expression A+B*C into a postfix expression using stack.

Now let us see another example, by transforming infix expression A*(B+C) into a postfix expression using stack.

Demo program

Now we ll demonstrate the use of stack to convert infix expression to postfix expression and then evaluate the postfix expression.

package com.tutorialspoint.expression;

pubpc class Stack {

   private int size;           
   private int[] intArray;     
   private int top;            

   //Constructor
   pubpc Stack(int size){
      this.size = size;           
      intArray = new int[size];   
      top = -1;                   
   }

   //push item on the top of the stack
   pubpc void push(int data) {
      if(!isFull()){
         //increment top by 1 and insert data
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   //pop item from the top of the stack
   pubpc int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   //view the data at top of the stack
   pubpc int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   //return true if stack is full
   pubpc boolean isFull(){
      return (top == size-1);
   }

   //return true if stack is empty
   pubpc boolean isEmpty(){
      return (top == -1);
   }
}

InfixToPostFix.java

package com.tutorialspoint.expression;

pubpc class InfixToPostfix {
   private Stack stack;
   private String input = "";
   private String output = "";

   pubpc InfixToPostfix(String input){
      this.input = input;
      stack = new Stack(input.length());
   }

   pubpc String translate(){
      for(int i=0;i<input.length();i++){
         char ch = input.charAt(i);
            switch(ch){
               case  + :
               case  - :
                  gotOperator(ch, 1);
                  break;
               case  * :
               case  / :
                  gotOperator(ch, 2);
                  break;
               case  ( :
                  stack.push(ch);
                  break;
               case  ) :
                  gotParenthesis(ch);
                  break;
               default:
                  output = output+ch;            
                  break;
          }
      }

      while(!stack.isEmpty()){
         output = output + (char)stack.pop();
      }       

      return output;
   }   

      //got operator from input
      pubpc void gotOperator(char operator, int precedence){
      while(!stack.isEmpty()){
         char prevOperator = (char)stack.pop();
         if(prevOperator ==  ( ){
            stack.push(prevOperator);
            break;
         }else{
            int precedence1;
            if(prevOperator ==  +  || prevOperator ==  - ){
               precedence1 = 1;
            }else{
               precedence1 = 2;
            }

            if(precedence1 < precedence){
               stack.push(Character.getNumericValue(prevOperator));
               break;                        
            }else{
               output = output + prevOperator;
            }                
         }   
      }
      stack.push(operator);
   }

   //got operator from input
   pubpc void gotParenthesis(char parenthesis){
      while(!stack.isEmpty()){
         char ch = (char)stack.pop();
         if(ch ==  ( ){                
            break;
         }else{
            output = output + ch;               
         }   
      }        
   } 
}

PostFixParser.java

package com.tutorialspoint.expression;

pubpc class PostFixParser {
private Stack stack;
private String input;

pubpc PostFixParser(String postfixExpression){
   input = postfixExpression;
   stack = new Stack(input.length());
}

   pubpc int evaluate(){
      char ch;
      int firstOperand;
      int secondOperand;
      int tempResult;

      for(int i=0;i<input.length();i++){
         ch = input.charAt(i);

         if(ch >=  0  && ch <=  9 ){
            stack.push(Character.getNumericValue(ch));
         }else{
            firstOperand = stack.pop();
            secondOperand = stack.pop();
            switch(ch){
               case  + :
                  tempResult = firstOperand + secondOperand;
                  break;
               case  - :
                  tempResult = firstOperand - secondOperand;
                  break;
               case  * :
                  tempResult = firstOperand * secondOperand;
                  break;
               case  / :
                  tempResult = firstOperand / secondOperand;
                  break;   
               default:
                  tempResult = 0;
            }
            stack.push(tempResult);
         }
      }
      return stack.pop();
   }       
}

PostFixDemo.java

package com.tutorialspoint.expression;

pubpc class PostFixDemo {
   pubpc static void main(String args[]){
      String input = "1*(2+3)";
      InfixToPostfix translator = new InfixToPostfix(input);
      String output = translator.translate();
      System.out.println("Infix expression is: " + input);
      System.out.println("Postfix expression is: " + output);

      PostFixParser parser = new PostFixParser(output);
      System.out.println("Result is: " + parser.evaluate());
   }
}

If we compile and run the above program then it would produce following result −

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5