calculateur de code leet code II

Question

C'est un problème qui se pose sur le code leet pour une simple calculatrice. Le problème est énoncé comme suit -

Implémentez une calculatrice de base pour évaluer une chaîne d'expression simple.

La chaîne d'expression contient uniquement des entiers non négatifs, des opérateurs +, -, *, / et des espaces vides. La division entière doit être tronquée vers zéro.

Exemple 1:

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

Exemple 2:

Input: " 3/2 "
Output: 1

Exemple 3:

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

Remarque: vous pouvez supposer que l'expression donnée est toujours valide. N'utilisez pas la fonction de bibliothèque intégrée eval.

C'est le code que j'ai écrit en peu de temps, je ne l'ai pas conçu pour des cas plus compliqués -

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);
    }
}

Étant donné qu'il n'y a pas de nombres négatifs dans l'expression, ce code fonctionne correctement et les cas de test ont tous réussi. Comment puis-je améliorer ce code?

Answer 1

Une remarque supplémentaire sur validate().

Vous avez trois cas de sortie:

• invalide
• nombre
• opérateur

Au lieu de les coder sous forme d'entiers (ce qui n'est pas un choix naturel naturel, car vous ne pouvez pas les ajouter, les soustraire ou les multiplier de manière significative), j'introduirais une énumération:

enum Validation { INVALID, NUMBER, OPERATOR }

Ensuite, la validate()méthode lit

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

Astuce: chaque fois que vous estimez nécessaire d'expliquer la signification de certains nombres, envisagez plutôt d'introduire une énumération. Vous bénéficiez de nombreux avantages sans inconvénients importants.

Answer 2

Pensez à utiliser le Dequeau lieu duStack

Comme indiqué dans la documentation , l'utilisation de Deque. Vous pouvez avoir plus d'informations sur SO .

Remplacez la forboucle par une boucle «for» améliorée

Dans votre code, vous n'avez pas réellement besoin de l'index fourni par la boucle, vous pouvez la version améliorée.

Avant

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

Après

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

Simplifiez les conditions booléennes.

Généralement, lorsque vous renvoyez les deux trueet falseentouré d'une condition, vous savez que vous pouvez refactoriser la logique de l'expression.

Avant

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

return false;

Après

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

Solution#validate méthode

1. Je vous suggère d'extraire la logique pour vérifier si le nombre est un opérateur / nombre est deux méthodes distinctes; cela rendra le code plus court et plus facile à lire.
2. La logique peut être simplifiée, vous pouvez supprimer le !(isNumber || isOperator)et si aucun des deux, la méthode retournera -1.
3. Le operand != '/' || operand !='*' || operand !='+' || operand != '-'est imparfait; retournera toujours vrai.

// -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

Avez-vous envisagé d'utiliser une seule pile?

Vous pouvez envelopper vos nombres dans une entrée constante qui renvoie le nombre. Et créez une entrée d'opération pour chaque opération valide. Pour que vous puissiez "simplement" réduire votre pile jusqu'à ce qu'elle ait un objet.

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;
}