calculadora de código leet código II
Este es un problema que se solicita en el código leet para una calculadora simple. El problema se plantea de la siguiente manera:
Implemente una calculadora básica para evaluar una cadena de expresión simple.
La cadena de expresión contiene solo números enteros no negativos, operadores +, -, *, / y espacios vacíos. La división de enteros debería truncar hacia cero.
Ejemplo 1:
Input: "3+2*2"
Output: 7
Ejemplo 2:
Input: " 3/2 "
Output: 1
Ejemplo 3:
Input: " 3+5 / 2 "
Output: 5
Nota: puede suponer que la expresión dada siempre es válida. No utilice la función de biblioteca integrada eval.
Este es el código que escribí en un corto período de tiempo, no lo diseñé para casos más complicados.
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);
}
}
Teniendo en cuenta que no hay números negativos en la expresión, este código funciona bien y todos los casos de prueba han pasado. ¿Cómo puedo mejorar este código?
Respuestas
Un comentario adicional sobre validate().
Tiene tres casos de salida:
- inválido
- número
- operador
En lugar de codificarlos como números enteros (que no es una elección natural, ya que no se pueden sumar, restar o multiplicar de manera significativa), introduciría una enumeración:
enum Validation { INVALID, NUMBER, OPERATOR }
Entonces el validate()método dice
public Validation validate(char operand) {
...
}
Sugerencia: siempre que crea necesario explicar el significado de algunos números, considere la posibilidad de introducir una enumeración. Obtienes muchos beneficios sin inconvenientes importantes.
Considere usar el en Dequelugar delStack
Como se indica en la documentación , Dequese prefiere el uso de . Puede tener más información sobre SO .
Reemplazar el forbucle con un bucle mejorado 'for'
En su código, en realidad no necesita el índice proporcionado por el bucle, puede la versión mejorada.
antes de
for (int i = 0; i < operArray.length; i++) {
//[...]
}
Después
for (char c : operArray) {
//[...]
}
Simplifica las condiciones booleanas.
Generalmente, cuando devuelve ambos truey está falserodeado por una condición, sabe que puede refactorizar la lógica de la expresión.
antes de
if (op2 == '*' && (op1 == '+' || op1 == '-')) {
return true;
}
return false;
Después
return op2 == '*' && (op1 == '+' || op1 == '-');
Solution#validate método
- Le sugiero que extraiga la lógica para verificar si el número es un operador / número es dos métodos separados; esto hará que el código sea más corto y más fácil de leer.
- La lógica se puede simplificar, puede eliminar el
!(isNumber || isOperator)y, si no, el método volverá-1. - El
operand != '/' || operand !='*' || operand !='+' || operand != '-'es defectuoso; siempre volverá verdadero.
// -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 == '-';
}
¿Ha considerado utilizar solo una pila?
Puede envolver sus números en una entrada constante que devuelva el número. Y cree una entrada de operación para cada operación válida. Para que puedas "simplemente" reducir tu pila hasta que tenga un artículo.
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;
}