Search code examples
javaif-statementwhile-loopoperator-precedence

Infix to postfix algorithm, the while statement I wrote is not being called out when it should


private Scanner sc = new Scanner(System.in);
private String expression;
private String exp[];
private ArrayList<String> post_fix = new ArrayList<>();
Stack<String> ope = new Stack<String>();
    public Model()
    {
        expression = sc.nextLine();
        
    }
    
    public void split()
    {
        
        //splitting the entered expression to array of operators alone and array of the numbers then create Arraylist to combine the operators and numbers together as if it is a string expression  but as an array
        String num[]= this.expression.split("[/+/*/-]");
        String preop[]= this.expression.split("[0-9]+");; // this will give [empty, operator, operator...] therefore we will create another array to fill in the ops excluding empty
        
        ArrayList<String> op = new ArrayList<>();//I used arraylist because easier
        for(int i = 1; i<preop.length;i++)
        {
            op.add(preop[i]);
        }
        
        //putting the operands and the operators together in the same array
                
        ArrayList<String> exp = new ArrayList<>();
       
        
        for(int i = 0; i <num.length;i++)
        {
            exp.add(num[i]);
        }
        int count = 0;
        for(int i = 0; i <op.size();i++)
        { //fill the arraylist with numbers then add the operators to it by using number (index of the operator +1 +count)
            exp.add(i+1+count, op.get(i)); //This is why arraylist was used in order to let values to be placed in between 
            count++;
            //i+1+count is used because index of the operator is in between two numbers meaning it is after the first index in num array so i+1 and because array keeps increasing, we do +count for the other operators to be placed in
        }
        
        this.exp = new String[exp.size()]; // we change the arraylist exp to instance array for faster operations later on
        System.out.print("Test to check if expression is converted into array as intented: ");
        for(int i = 0; i<this.exp.length;i++)
        {
            this.exp[i] = exp.get(i);
            System.out.print(this.exp[i]);
        }
        System.out.println();
      
    }
    
    public void postfix()
    {
    
        for(int i = 0; i < exp.length; i++)
        {
            if(i%2 == 0)//since operands are observed to always have even index in the array
            {
                post_fix.add(exp[i]);
                System.out.println(post_fix);
            }
            else 
            {
                boolean x = !ope.empty();
                System.out.println("Test of !ope.empty: " + x);
                while(!ope.empty()&& HasHigherPrecedence(ope.peek(), this.exp[i]))
                {
                    post_fix.add(ope.peek());
                    ope.pop();
                    
                    
                }
                ope.push(exp[i]);
                System.out.println("stack_top: "+ ope.peek());
            }
            
    
        }
        while(!ope.empty())
        {
            
            post_fix.add(ope.peek());
            ope.pop();
        }
        System.out.println("Output: " +post_fix);
    
        
    }
    
    public String getPost_fix()
    {
        String temp = "";
        for(int i =0; i < exp.length;i++)
        {
            temp = temp + post_fix.get(i);
        }
    
        return temp;
    }
    
    public double evaluate() 
    {
        return 0;
    }
    
    private boolean HasHigherPrecedence(String op1, String op2)
    {
        //op1 is operator 1 at the top of the stack thus associativity highest
        int a_op1 = 1;
        int a_op2 = 0;
        
        int p_op1 = 0;
        int p_op2= 0;
        //the precedence will be measured with numbers
        String operators[]= {"","+","-","*","/"};
        int precedence[] = {0,1,1,2,2}; //the reason for blank operator and 0 precedence is because the stack initially will be empty
        for(int i = 0; i< operators.length;i++)
        {
            if(op1.equals(operators[i]))
            {
                p_op1=precedence[i];
            }
        }
        for(int i = 0; i< operators.length;i++)
        {
            if(op2.equals(operators[i]))
            {
                p_op2=precedence[i];
            }
        }
        
        boolean higher_ornot = false;
        
        if(p_op1 > p_op2)
        {
            higher_ornot = false;
        }
        else if(p_op1 < p_op1)
        {
            higher_ornot = true;
        }
        else if(p_op1== p_op2)
        {
        System.out.println(op1+": "+p_op1);
        System.out.println(op2+": "+p_op2);
            higher_ornot = false; //since associativity of op1 will be higher --> thus higher precedence
        }
        
        return higher_ornot;
    }
    
}

Output of the code

I am trying to converst user's infix mathmatical expression into a postfix expression in an array that will be evaluated but before evaluation, I faced a problem in the postfix method

while(!ope.empty()&& HasHigherPrecedence(ope.peek(), this.exp[i]))

This specific line is not being called out when the condition should be true, when it is comparing top of the stack which is * to - and * has higher precedence and since stack is not empty thus it should return true thus the function is called. I tested if I have any errors other areas but everything I tested was correct, I really have no clue how to fix.

I am really clueless even after 1hour and a half staring and trying to trace the code

I am expecting from output to be [3, 2, 4, *, +, 3, -] which is the postfix expression that technically will be evaluated later


Solution

  • the reason is that the second condition HasHigherPrecedence is false in all cases, so even if the stack is non empty the whole condition is evaluated to false