leet code calculator II kod
Jest to problem, który pojawia się w kodzie leet dla prostego kalkulatora. Problem jest następujący -
Zaimplementuj podstawowy kalkulator, aby oszacować prosty ciąg wyrażenia.
Ciąg wyrażenia zawiera tylko nieujemne liczby całkowite, operatory +, -, *, / i puste spacje. Dzielenie całkowite powinno zostać obcięte w kierunku zera.
Przykład 1:
Input: "3+2*2"
Output: 7
Przykład 2:
Input: " 3/2 "
Output: 1
Przykład 3:
Input: " 3+5 / 2 "
Output: 5
Uwaga: Możesz założyć, że dane wyrażenie jest zawsze prawidłowe. Nie używaj wbudowanej funkcji biblioteki eval.
To jest kod, który napisałem w krótkim czasie, nie projektowałem go dla bardziej skomplikowanych przypadków -
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);
}
}
Biorąc pod uwagę, że w wyrażeniu nie ma liczb ujemnych, ten kod działa dobrze, a wszystkie przypadki testowe przeszły pomyślnie. Jak mogę ulepszyć ten kod?
Odpowiedzi
Jedna dodatkowa uwaga na temat validate().
Masz trzy przypadki wyjściowe:
- nieważny
- numer
- operator
Zamiast kodować je jako liczby całkowite (co nie jest naturalnym wyborem, ponieważ nie można ich sensownie dodawać, odejmować ani mnożyć), wprowadziłbym wyliczenie:
enum Validation { INVALID, NUMBER, OPERATOR }
Następnie validate()metoda czyta
public Validation validate(char operand) {
...
}
Wskazówka: kiedykolwiek uznasz, że konieczne jest wyjaśnienie znaczenia niektórych liczb, rozważ zamiast tego wprowadzenie wyliczenia. Otrzymujesz wiele korzyści bez żadnych znaczących wad.
Rozważ użycie DequezamiastStack
Jak stwierdzono w dokumentacji , Dequepreferowane jest użycie . Możesz uzyskać więcej informacji na temat SO .
Zastąp forpętlę rozszerzoną pętlą „for”
W swoim kodzie tak naprawdę nie potrzebujesz indeksu dostarczonego przez pętlę, możesz skorzystać z ulepszonej wersji.
Przed
for (int i = 0; i < operArray.length; i++) {
//[...]
}
Po
for (char c : operArray) {
//[...]
}
Uprość warunki logiczne.
Ogólnie rzecz biorąc, gdy zwracasz oba truei falseotoczone przez warunek, wiesz, że możesz refaktoryzować logikę wyrażenia.
Przed
if (op2 == '*' && (op1 == '+' || op1 == '-')) {
return true;
}
return false;
Po
return op2 == '*' && (op1 == '+' || op1 == '-');
Solution#validate metoda
- Proponuję wyodrębnić logikę, aby sprawdzić, czy liczba jest operatorem / liczba to dwie oddzielne metody; dzięki temu kod będzie krótszy i łatwiejszy do odczytania.
- Logikę można uprościć, można usunąć,
!(isNumber || isOperator)a jeśli nie, metoda zwróci-1. operand != '/' || operand !='*' || operand !='+' || operand != '-'Jest błędna; zawsze zwróci prawdę.
// -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 == '-';
}
Czy rozważałeś użycie tylko jednego stosu?
Możesz zawrzeć swoje liczby w stałą pozycję, która zwraca liczbę. I utwórz jeden wpis operacji dla każdej prawidłowej operacji. Abyś mógł „po prostu” zmniejszyć swój stos, aż będzie miała jeden przedmiot.
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;
}