leet code calculator II code
Este é um problema que surge no código leet de uma calculadora simples. O problema é expresso da seguinte forma -
Implemente uma calculadora básica para avaliar uma string de expressão simples.
A string de expressão contém apenas inteiros não negativos, operadores +, -, *, / e espaços vazios. A divisão inteira deve truncar em direção a zero.
Exemplo 1:
Input: "3+2*2"
Output: 7
Exemplo 2:
Input: " 3/2 "
Output: 1
Exemplo 3:
Input: " 3+5 / 2 "
Output: 5
Nota: Você pode assumir que a expressão fornecida é sempre válida. Não use a função de biblioteca interna eval.
Este é o código que escrevi em um curto espaço de tempo, não o projetei para casos mais 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);
}
}
Considerando que não há números negativos na expressão, esse código funciona bem e todos os casos de teste foram aprovados. Como posso melhorar este código?
Respostas
Uma observação adicional sobre validate().
Você tem três casos de saída:
- inválido
- número
- operador
Em vez de codificá-los como inteiros (o que não é uma escolha natural natural, já que você não pode adicionar, subtrair ou multiplicar de forma significativa), eu introduziria um enum:
enum Validation { INVALID, NUMBER, OPERATOR }
Então o validate()método lê
public Validation validate(char operand) {
...
}
Dica: sempre que achar necessário explicar o significado de alguns números, considere a introdução de um enum. Você obtém muitos benefícios sem desvantagens significativas.
Considere usar o em Dequevez doStack
Conforme declarado na documentação , o uso do Dequeé preferido. Você pode ter mais informações sobre o SO .
Substitua o forloop por um loop 'para' aprimorado
Em seu código, você não precisa realmente do índice fornecido pelo loop, você pode da versão aprimorada.
Antes
for (int i = 0; i < operArray.length; i++) {
//[...]
}
Depois de
for (char c : operArray) {
//[...]
}
Simplifique as condições booleanas.
Geralmente, quando você está retornando ambos truee falsecercado por uma condição, sabe que pode refatorar a lógica da expressão.
Antes
if (op2 == '*' && (op1 == '+' || op1 == '-')) {
return true;
}
return false;
Depois de
return op2 == '*' && (op1 == '+' || op1 == '-');
Solution#validate método
- Eu sugiro que você extraia a lógica para verificar se o número é um operador / número são dois métodos separados; isso tornará o código mais curto e fácil de ler.
- A lógica pode ser simplificada, você pode remover o
!(isNumber || isOperator)e, se nenhum, o método retornará-1. - O
operand != '/' || operand !='*' || operand !='+' || operand != '-'é defeituoso; sempre retornará verdadeiro.
// -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 == '-';
}
Você considerou usar apenas uma pilha?
Você pode agrupar seus números em uma entrada constante que retorna o número. E crie uma entrada de operação para cada operação válida. Para que você possa "apenas" reduzir sua pilha até que ela tenha um 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;
}