Leet Code Rechner II Code

Question

Dies ist ein Problem, das im Leet-Code für einen einfachen Taschenrechner gestellt wird. Das Problem wird wie folgt angegeben:

Implementieren Sie einen Basisrechner, um eine einfache Ausdruckszeichenfolge auszuwerten.

Die Ausdruckszeichenfolge enthält nur nicht negative Ganzzahlen, +, -, *, / Operatoren und Leerzeichen. Die Ganzzahldivision sollte gegen Null abgeschnitten werden.

Beispiel 1:

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

Beispiel 2:

Input: " 3/2 "
Output: 1

Beispiel 3:

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

Hinweis: Sie können davon ausgehen, dass der angegebene Ausdruck immer gültig ist. Verwenden Sie nicht die in eval integrierte Bibliotheksfunktion.

Dies ist der Code, den ich in kurzer Zeit geschrieben habe. Ich habe ihn nicht für kompliziertere Fälle entworfen.

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

Da der Ausdruck keine negativen Zahlen enthält, funktioniert dieser Code einwandfrei und alle Testfälle sind bestanden. Wie kann ich diesen Code verbessern?

Answer 1

Eine zusätzliche Bemerkung zu validate().

Sie haben drei Ausgabefälle:

• ungültig
• Nummer
• Operator

Anstatt sie als Ganzzahlen zu codieren (was keine natürliche natürliche Wahl ist, da Sie sie nicht sinnvoll addieren, subtrahieren oder multiplizieren können), würde ich eine Aufzählung einführen:

enum Validation { INVALID, NUMBER, OPERATOR }

Dann validate()liest die Methode

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

Hinweis: Wenn Sie es für notwendig halten, die Bedeutung einiger Zahlen zu erklären, sollten Sie stattdessen eine Aufzählung einführen. Sie erhalten viele Vorteile ohne wesentliche Nachteile.

Answer 2

Erwägen Sie die Verwendung von Dequeanstelle vonStack

Wie in der Dokumentation angegeben , wird die Verwendung von Dequebevorzugt. Sie können weitere Informationen zu SO haben .

Ersetzen Sie die forSchleife durch eine erweiterte 'for'-Schleife

In Ihrem Code benötigen Sie nicht den von der Schleife bereitgestellten Index, sondern die erweiterte Version.

Vor

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

Nach dem

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

Vereinfachen Sie die booleschen Bedingungen.

Wenn Sie beide zurückgeben trueund falsevon einer Bedingung umgeben sind, wissen Sie im Allgemeinen, dass Sie die Logik des Ausdrucks umgestalten können.

Vor

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

return false;

Nach dem

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

Solution#validate Methode

1. Ich schlage vor, dass Sie die Logik extrahieren, um zu überprüfen, ob die Zahl ein Operator ist / die Zahl zwei separate Methoden ist; Dadurch wird der Code kürzer und leichter lesbar.
2. Die Logik kann vereinfacht werden, Sie können die entfernen !(isNumber || isOperator)und wenn keine, wird die Methode zurückgegeben -1.
3. Das operand != '/' || operand !='*' || operand !='+' || operand != '-'ist fehlerhaft; wird immer true zurückgeben.

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

Haben Sie in Betracht gezogen, nur einen Stapel zu verwenden?

Sie können Ihre Zahlen in einen konstanten Eintrag einschließen, der die Zahl zurückgibt. Erstellen Sie für jede gültige Operation einen Operationseintrag. Damit Sie Ihren Stapel "nur" reduzieren können, bis sie einen Gegenstand hat.

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