leet code calculator II code

Question

This is a problem that is asked on leet code for a simple calculator. The problem is stated as follows -

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note: You may assume that the given expression is always valid. Do not use the eval built-in library function.

This is the code I wrote in a short span of time, I did not design it for more complicated cases -

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;
import java.lang.Exception;

public class Solution{
    
    Stack<Integer> numberStack = new Stack();
    Stack<Character> operatorStack = new Stack();
    
    //assuming op1 is in operator stack and op2 is to be inserted
    public boolean hasPrecedence(char op1, char op2){
        if (op2 == '/' && op1 != '/'){
            return true;
        }
        
        if (op2 == '*' && (op1 == '+' || op1 == '-')){
            return true;
        }
        
        return false;
    }
    
    // -1 means invalid
    //  0 means number
    //  1 means an operator
    public int validate(char operand){
        boolean isNumber = false;
        if (Character.isDigit(operand)){
            isNumber = true; 
        }
        boolean isOperator = false;
        if (operand != '/' || operand !='*' || operand !='+' || operand != '-'){
            isOperator = true;
        }
        
        if (!(isNumber || isOperator)){
            return -1;
        }
        
        if (isNumber){
            return 0;
        }
        
        if (isOperator){
            return 1;
        }
        
        return -1;
    }
    
    private void performOperation(){
        if(operatorStack.empty() || numberStack.empty()){
            return;
        }
        char operator = operatorStack.pop();
        if(numberStack.size() < 2){
            return;
        }
        int num2 = numberStack.pop();
        int num1 = numberStack.pop();
        int result = 0;
        switch(operator){
            case '/': result = num1/num2;
                      numberStack.push(result);
                      break;
            case '+': result = num1+num2;
                      numberStack.push(result);
                      break;
            case '*': result = num1*num2;
                      numberStack.push(result);
                      break;
            case '-': result = num1-num2;
                      numberStack.push(result);
                      break;
        }         
            
    }
            
    private int calculate(String exp) throws Exception{
        
        if (exp == null || exp.trim().length() == 0 ){
            throw new Exception("Null or empty expression ");
        }
        char[] operArray = exp.toCharArray();
        StringBuffer numberBuffer = new StringBuffer();
        
        
        char operand = '\0';
        for (int i=0; i < operArray.length ; i++){
            operand = operArray[i];
            if (Character.isWhitespace(operand)){
                continue;
            }
            int opVal = -1;
            opVal = validate(operand);
            if (opVal == -1){
                throw new Exception("Invalid inputs ");
            }
            
            //current char is number
            if (opVal == 0){
                numberBuffer.append(operand);
                continue;
            }
            
            if (opVal == 1){
                numberStack.push(Integer.parseInt(numberBuffer.toString()));
                numberBuffer = new StringBuffer();
            
                if (!operatorStack.empty()){
                    if(!hasPrecedence(operatorStack.peek(), operand)){
                        performOperation();
                    }
                }
                    operatorStack.push(operand);
            }
        }
        
        numberStack.push(Integer.parseInt(numberBuffer.toString()));
        while(!operatorStack.isEmpty()){
            performOperation();
        }
        return numberStack.pop();
    }

    public static void main(String []args) throws Exception{
        Solution expparser = new Solution();
        int result = expparser.calculate("3+2*2");
        System.out.println("result is " + result);
        result = expparser.calculate(" 3/2 ");
        System.out.println("result is " + result);
        result = expparser.calculate(" 3+5 / 2 ");
        System.out.println("result is " + result);
        result = expparser.calculate("3+2-2");
        System.out.println("result is " + result);
        result = expparser.calculate(" 3/2-1 ");
        System.out.println("result is " + result);
        result = expparser.calculate(" 3/5/2 ");
        System.out.println("result is " + result);
        result = expparser.calculate("3/5*2");
        System.out.println("result is " + result);
        result = expparser.calculate("3*5*2");
        System.out.println("result is " + result);
        result = expparser.calculate(" 3+5+2 ");
        System.out.println("result is " + result);
    }
}

Considering there are no negative numbers in the expression, this code works fine and the test cases have all passed. How can I improve this code?

Answer 1

One additional remark on validate().

You have three output cases:

• invalid
• number
• operator

Instead of encoding them as integers (which is not a natural natural choice, as you can't meaningfully add, subtract or multiply them), I'd introduce an enum:

enum Validation { INVALID, NUMBER, OPERATOR }

Then the validate() method reads

public Validation validate(char operand) {
    ...
}

Hint: whenever you feel it necessary to explain the meaning of some numbers, consider introducing an enum instead. You get a lot of benefits without any significant downsides.

Answer 2

Consider using the Deque instead of the Stack

As stated in the documentation, the use of the Deque is preferred. You can have more information on SO.

Replace the for loop with an enhanced 'for' loop

In your code, you don’t actually need the index provided by the loop, you can the enhanced version.

Before

for (int i = 0; i < operArray.length; i++) {
   //[...]
}

After

for (char c : operArray) {
   //[...]
}

Simplify the boolean conditions.

Generally, when you are returning both true and false surrounded by a condition, you know you can refactor the logic of the expression.

Before

if (op2 == '*' && (op1 == '+' || op1 == '-')) {
   return true;
}

return false;

After

return op2 == '*' && (op1 == '+' || op1 == '-');

Solution#validate method

1. I suggest that you extract the logic to check if the number is an operator / number is two separate methods; this will make the code shorter and easier to read.
2. The logic can be simplified, you can remove the !(isNumber || isOperator) and if neither, the method will return -1.
3. The operand != '/' || operand !='*' || operand !='+' || operand != '-' is flawed; will always return true.

// -1 means invalid
//  0 means number
//  1 means an operator
public int validate(char operand) {
   boolean isNumber = isNumber(operand);
   boolean isOperator = isOperator(operand);

   if (isNumber) {
      return 0;
   } else if (isOperator) {
      return 1;
   }

   return -1;
}

private boolean isNumber(char operand) {
   return Character.isDigit(operand);
}

private boolean isOperator(char operand) {
   return operand == '/' || operand == '*' || operand == '+' || operand == '-';
}

Answer 3

Do you have considered to use only one stack ?

You can wrap your numbers into a constant entry that returns the number. And create one operation entry for each valid operation. So that you can "just" reduce your stack until she has one item.

Stack<Function<Integer, Integer>> operations = new Stack<>();


public Integer resolve(final Integer x) {
    Integer right = x;
    while ( !operations.isEmpty() ) {
        right = operations.pop().apply(right);
    }
    return right;
}