codice leet calcolatore II codice
Questo è un problema che viene chiesto sul codice leet per una semplice calcolatrice. Il problema è indicato come segue:
Implementa una calcolatrice di base per valutare una semplice stringa di espressione.
La stringa dell'espressione contiene solo numeri interi non negativi, operatori +, -, *, / e spazi vuoti. La divisione intera dovrebbe essere troncata verso zero.
Esempio 1:
Input: "3+2*2"
Output: 7
Esempio 2:
Input: " 3/2 "
Output: 1
Esempio 3:
Input: " 3+5 / 2 "
Output: 5
Nota: puoi presumere che l'espressione data sia sempre valida. Non utilizzare la funzione di libreria incorporata eval.
Questo è il codice che ho scritto in un breve lasso di tempo, non l'ho progettato per casi più complicati -
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);
}
}
Considerando che non ci sono numeri negativi nell'espressione, questo codice funziona bene e tutti i casi di test sono passati. Come posso migliorare questo codice?
Risposte
Un'ulteriore osservazione validate().
Hai tre casi di output:
- non valido
- numero
- operatore
Invece di codificarli come numeri interi (che non è una scelta naturale naturale, poiché non è possibile sommarli, sottrarli o moltiplicarli in modo significativo), introdurrei un'enumerazione:
enum Validation { INVALID, NUMBER, OPERATOR }
Quindi il validate()metodo legge
public Validation validate(char operand) {
...
}
Suggerimento: ogni volta che ritieni necessario spiegare il significato di alcuni numeri, considera invece di introdurre un enum. Ottieni molti vantaggi senza svantaggi significativi.
Considera l' Dequeidea di utilizzare invece diStack
Come indicato nella documentazione , Dequeè preferibile l'uso di . Puoi avere maggiori informazioni su SO .
Sostituisci il forciclo con un ciclo "for" migliorato
Nel tuo codice, in realtà non hai bisogno dell'indice fornito dal loop, puoi la versione migliorata.
Prima
for (int i = 0; i < operArray.length; i++) {
//[...]
}
Dopo
for (char c : operArray) {
//[...]
}
Semplifica le condizioni booleane.
In genere, quando si restituiscono entrambi truee si è falsecircondati da una condizione, si sa che è possibile eseguire il refactoring della logica dell'espressione.
Prima
if (op2 == '*' && (op1 == '+' || op1 == '-')) {
return true;
}
return false;
Dopo
return op2 == '*' && (op1 == '+' || op1 == '-');
Solution#validate metodo
- Ti suggerisco di estrarre la logica per verificare se il numero è un operatore / numero è due metodi separati; questo renderà il codice più breve e più facile da leggere.
- La logica può essere semplificata, è possibile rimuovere il
!(isNumber || isOperator)e se nessuno dei due, il metodo tornerà-1. - Il
operand != '/' || operand !='*' || operand !='+' || operand != '-'è viziata; restituirà sempre vero.
// -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 == '-';
}
Hai considerato di utilizzare solo una pila?
Puoi racchiudere i tuoi numeri in una voce costante che restituisce il numero. E creare una voce di operazione per ogni operazione valida. In modo che tu possa "semplicemente" ridurre la tua pila finché non ha un oggetto.
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;
}