SPOJ CMEXPR Program

Question

I am trying to solve this problem SPOJ CMEXPR. I found out that the algorithm to this problem is:

1. First convert expression into Postfix Expression (Reverse Polish Notation)
2. Then convert Postfix Expression into Infix Expression.

I have successfully completed the first step but getting problem in second step. It doesn't throw any Exception it just give improper output.

Here is my code:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

class RPN{
    public String expression;
    public String output;
    public Queue<Character> queue; 

    public RPN(String exp){
        this.expression = exp;
        processRPN();
    }

    private void processRPN(){
        System.out.println("Original Infix Expression ==> " + expression);
        Queue<Character> queue = new LinkedList<Character>();
        Stack<Character> stack = new Stack<Character>();
        for(int i=0; i < expression.length(); i++){
            Character op = new Character(expression.charAt(i));
            if(op.equals('/') || op.equals('*') || op.equals('+') || op.equals('-') || op.equals('^') || op.equals('(')){
                stack.push(op);
            }
            else if(op == ')'){
                while(!stack.peek().equals('(')){
                    queue.add(stack.pop());
                }
                stack.pop();
            }
            else{
                queue.add(op);
            }
        }
        while(!stack.isEmpty()){
            queue.add(stack.pop());
        }
        displayQueue(queue);
    }   

    private void displayQueue(Queue<Character> queue){
        this.output = queue.toString();
        this.queue = queue;
    }

    public Queue<Character> getPostFixExpressionQueue(){
        return queue;
    }
}

class PIN{
    public Stack<String> finalOutputStack;
    public Queue<Character> queue;
    public static Map<Character, Integer> precedenceMap = new HashMap<Character, Integer>();    

    static{
        precedenceMap.put('-',1);
        precedenceMap.put('+',2);
        precedenceMap.put('*',3);
        precedenceMap.put('/',4);
        precedenceMap.put('^',4);
    }

    public PIN(Queue<Character> queue){
        this.queue = queue;
        processPIN();
    }

    private void processPIN(){
        System.out.println("Postfix to Infix Process Starts...");
        Character prevOp = null, currOp = null;
        Stack<String> stack = new Stack<String>();
        while(!queue.isEmpty()){
            Character peekCh = queue.peek();
            if(peekCh.equals('/') || peekCh.equals('*') || peekCh.equals('^') || peekCh.equals('+') || peekCh.equals('-')){
                if(prevOp == null && currOp == null){
                    prevOp = queue.peek();
                    currOp = queue.poll();
                }
                else{
                    prevOp = currOp;
                    currOp = queue.poll();
                }
                if(precedenceMap.get(currOp) < precedenceMap.get(prevOp)){
                    String operand2 = stack.pop();
                    String operand1 = stack.pop();
                    stack.push("("+operand1+")"+currOp.toString()+operand2);
                }
                else{
                    String operand2 = stack.pop();
                    String operand1 = stack.pop();
                    stack.push(operand1+currOp.toString()+operand2);                    
                }
            }
            else{
                stack.push(queue.poll().toString());
            }
        }
        storeOutput(stack);
    }

    private void storeOutput(Stack<String> stack){
        this.finalOutputStack = stack;
    }   
}

public class Test{
    public static void main(String h[]){
        RPN rpnObj = new RPN("(a+b)-(c-d)-(e/f)");
        System.out.println("Postfix Notation ==> " + rpnObj.output);
        PIN pinObj = new PIN(rpnObj.getPostFixExpressionQueue());
        System.out.println("Expression with Minimum Parenthesis ==> " + pinObj.finalOutputStack.toString());
    }
}

Answer 1

Problem 1

Your algorithm for constructing the Reverse-Polish-Notation produces incorrect results on some inputs. Specifically, it interprets all operators as right-associative and it does not take operator precedence into account.

Regarding right-associativity, consider the input a-b-c. Your algorithm incorrectly constructs abc--, whereas the correct result is ab-c-. This means your algorithm incorrectly interprets the input as a-(b-c). This interpretation is a right-associative interpretation of -, whereas the left-associative interpretation would be (a-b)-c, which preserves the intended meaning of the input a-b-c.

Regarding operator precedence, consider the input a*b+c. Your algorithm incorrectly constructs abc+*. This means your algorithm has given the last operator + a higher precedence than the first operator *, interpreting the input as a*(b+c). The correct result would be ab*c+, which corresponds to the interpretation (a*b)+c.

The algorithm you need for correctly constructing the Reverse-Polish-Notation from the Infix-Notation is known as Shunting-Yard-Algorithm. See for example here for how to implement it in Java.

Problem 2

Once you have obtained the correct Reverse-Polish-Notation, there is another problem in your algorithm for reconstructing the Infix-Notation. Your approach is to insert bracket around the left side of an operator, based on some condition. This approach cannot give the correct result in all cases. Consider for example (a+b)*(c+d). The Reverse-Polish-Notation would be ab+cd+*. Brackets are needed around each of the additions, but your approach only allows to insert brackets around the left side of the *, not the right side.

Also, your condition for whether to insert brackets is based on comparing the current operator with the previous operator in the left-to-right traversal of the Reverse-Polish-Notation. This approach is also incorrect, in that the previous operator may be completely unrelated to the current operator. Consider again ab+cd+*. When you look at the second +, the previous operator would be the first +, but these are completely unrelated, because they occur at different branches in the parse tree of the expression.

To fix this, you should first track the previous operator for each element on the stack, instead of tracking the previous operator in the left-to-right traversal. You could do this either by extending the result stack to hold a pair of previous operator and result string. Or you could keep a second stack that only tracks the previous operator for each entry on the result stack.

Second, you should apply the operator precedence check for both the left and the right side of the operation, and insert brackets accordingly. Note that the rules for inserting brackets are not symmetric for the left and right operand. For example, when the current operand is -, no bracket is needed for the left operand in all cases, but for the right operand a bracket is needed if the previous operator was + or -.

Here is an example:

class PIN {

  static boolean preceedsLeft(char prevOp, char currOp) {
    if (currOp == '*' || currOp == '/') {
      if (prevOp == '+' || prevOp == '-') {
        return true;
      }
    }

    return false;
  }

  static boolean preceedsRight(char prevOp, char currOp) {
    if (currOp == '-' || currOp == '*') {
      if (prevOp == '+' || prevOp == '-') {
        return true;
      }
    }

    if (currOp == '/') {
      if (prevOp == '+' || prevOp == '-' || prevOp == '*' || prevOp == '/') {
        return true;
      }
    }

    return false;
  }

  public static String process(Queue<Character> queue) {
    Stack<String> stack = new Stack<String>();
    Stack<Character> prevOp = new Stack<Character>();

    while (!queue.isEmpty()) {
      Character current = queue.poll();

      if (!current.equals('/') && !current.equals('*') &&
          !current.equals('+') && !current.equals('-')) {
        stack.push(current.toString());
        prevOp.push(current);
        continue;
      }

      Character prevOp2 = prevOp.pop();
      Character prevOp1 = prevOp.pop();

      String operand2 = stack.pop();
      String operand1 = stack.pop();

      if (preceedsLeft(prevOp1, current)) {
        operand1 = "(" + operand1 + ")";
      }

      if (preceedsRight(prevOp2, current)) {
        operand2 = "(" + operand2 + ")";
      }

      stack.push(operand1 + current + operand2);
      prevOp.push(current);
    }
    return stack.get(0);
  }
}