Java: Оценщик выражений стеков: исключение пустого стека при вычитании или умножении
Это несколько загруженный вопрос. Я пишу алгоритм оценщика Lisp, который принимает входные выражения, написанные, например, как:
(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))
Проблема в том, что выдает ошибку EmptyStack из-за операций (- 6) и (*)
Когда я пишу это как (- 0 6) и (* 1), оно корректно компилируется с правильным результатом. Я думаю, что он хочет вычесть из чего-то и умножить что-то (не может иметь никаких цифр). Это как-то связано со структурой оценки моего операнда. Я хочу реализовать это в самой программе, без необходимости вручную добавлять нули для вычитания и единицы для умножения. Есть идеи, как это сделать?
Я смотрел на это весь день и не могу понять, почему моя структура push / pop работает таким образом. Я попытался поэкспериментировать с регулярными выражениями, но, похоже, это не помогло.
Структура программы:
1) Используются два стека: expressionStack типа Object и currentOperationStack типа Double.
2) метод valuCurrentOperation() оценивает текущую операцию:
Извлекает операнды из expressionStack и помещает их в currentOperationStack, пока не найдет оператор.
Использует оператор для операндов в currentOperationStack.
Вставляет результат в expressionStack.
3) метод define () оценивает текущее выражение Lisp в inputExpression (используя сканер для чтения и операторы case для операндов) и возвращает результат.
import java.util.*;
public class LispEvaluator {
/**
* Input expression
*/
private String inputExp;
/**
* Stacks created for the main expression and current operation.
*/
private Stack<Object> expStack;
private Stack<Double> currentOpStack;
/**
* Default constructor initializes input and creates Stack objects.
*/
public LispEvaluator()
{
inputExp = "";
expStack = new Stack<Object>();
currentOpStack = new Stack<Double>();
}
/**
* Constructor sets inputExpr to inputExpression and creates Stack objects.
* @param inputExpression
* @throws LispEvaluatorException
*/
public LispEvaluator(String input_Expression) throws LispEvaluatorException
{
// If there is no expression, throws an exception.
if(input_Expression == null)
{
throw new LispEvaluatorException("Input statement is null.");
}
// Objects created
inputExp = input_Expression;
expStack = new Stack<Object>();
currentOpStack = new Stack<Double>();
}
/**
* evaluateCurrentOperation() method evaluates the current operation:
* - Pops operands from expStack and pushes them onto currentOpStack until it finds an operator.
* - Uses the operator on the operands on currentOpStack.
* - Pushes the result into exprStack.
*/
private void evaluateCurrentOperation()
{
String current_Operation;
boolean numeric = true;
// Do... while statement sets current operation (while it is numeric).
do{
current_Operation = (String.valueOf(expStack.pop()));
try{
Double number = Double.parseDouble(current_Operation);
currentOpStack.push(number);
}catch(NumberFormatException nfe){
numeric = false;
}
} while(numeric);
double result;
switch (current_Operation) {
case "*":
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result *= currentOpStack.pop();
}
break;
case "/":
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result /= currentOpStack.pop();
}
break;
case "+":
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result += currentOpStack.pop();
}
break;
case "-":
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result -= currentOpStack.pop();
}
break;
default:
result = currentOpStack.pop();
break;
}
expStack.push(result);
}
/**
* evaluate() method evaluates the current Lisp expression in inputExpr and returns the result.
* @throws LispEvaluatorException
*/
public double evaluate() throws LispEvaluatorException
{
Scanner inputExprScanner = new Scanner(inputExp);
/**
* Breaks the string into single characters using a delimiter.
*/
inputExprScanner = inputExprScanner.useDelimiter("\\s*");
/**
* Scans the tokens in the string (runs while there is a next token).
*/
while (inputExprScanner.hasNext())
{
/**
* If it has an operand, pushes operand object onto the exprStack.
*/
if (inputExprScanner.hasNextInt())
{
/**
* Scanner gets all of the digits (regular expression \\d+ means any digit).
*/
String dataString = inputExprScanner.findInLine("\\d+");
expStack.push(Double.parseDouble(dataString));
}
else
{
/**
* Gets one character in String token.
*/
String token = inputExprScanner.next();
char item = token.charAt(0);
switch(item)
{
// If "(", next token is an operator (so do nothing).
case '(':
break;
// If ")", it will evaluate that expression since parenthesis are closed.
case ')':
evaluateCurrentOperation();
break;
// If there is an operator "* + / -", then it pushes the operator onto exprStack.
case'*':
expStack.push("*");
break;
case'+':
expStack.push("+");
break;
case'/':
expStack.push("/");
break;
case'-':
expStack.push("-");
break;
/**
* Default throws an error.
*/
default:
throw new LispEvaluatorException(item + " is not a valid operator");
} // end switch
} // end else
} // end while
/**
* If you run out of tokens, the value on the top of exprStack is the result of the expression.
*
*/
return Double.parseDouble(String.valueOf(expStack.pop()));
}
/**
* Reset method sets inputExpr to inputExpression and clears Stack objects.
* @param inputExpression
* @throws LispEvaluatorException
*/
public void reset(String inputExpression) throws LispEvaluatorException
{
if(inputExpression == null)
{
throw new LispEvaluatorException("Input statement is null");
}
inputExp = inputExpression;
expStack.clear();
currentOpStack.clear();
}
/**
* Test method to print the result of the expression evaluator.
* @param s
* @param expr
* @throws LispEvaluatorException
*/
private static void evaluateExprTest(String s, LispEvaluator expr) throws LispEvaluatorException
{
Double result;
System.out.println("Expression: " + s);
expr.reset(s);
result = expr.evaluate();
System.out.printf("Result: %.2f\n", result);
System.out.println("-------");
}
/**
* Main method uses test cases to test the evaluator.
* @param args
* @throws LispEvaluatorException
*/
public static void main (String args[]) throws LispEvaluatorException
{
LispEvaluator expr= new LispEvaluator();
/**
* Expressions are tested.
* Note: For each operation written as (- 6), in order for the Stack to continue,
* it needs to be written as (- 0 6). This way, it is subtracting from a digit.
*/
String test1 = "(+ 5 0 10)";
String test2 = "(+ 5 0 10 (- 7 2))";
String test3 = "(+ (- 0 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)))";
String test4 = "(+ (- 0 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1)))";
String test5 = "(+ 2 6) (* 12 18) (/ (+ 32) (* 1) (- 21 3 1))";
String test6 = "(+ 1 2 (- 5 1) (*4 11 14))";
evaluateExprTest(test1, expr);
evaluateExprTest(test2, expr);
evaluateExprTest(test3, expr);
evaluateExprTest(test4, expr);
evaluateExprTest(test5, expr);
evaluateExprTest(test6, expr);
}
}
Класс пользовательских исключений:
public class LispEvaluatorException extends Exception{
public LispEvaluatorException(String message) {
super(message);
}
}
1 ответ
Исправления довольно просты: сбои, которые вы получаете, заключаются в том, что унарные операции - это отличительные особенности, поэтому вам необходимо явно их кодировать.
Исправление этой проблемы состоит из двух частей:
- Добавить проверку на пустой стек до первого
pop() - Добавить чек на унарный минус
-и унарное деление/, которые имеют отдельные пути кода.
Вот часть кода, которую нужно исправить:
switch (current_Operation) {
case "*":
if (currentOpStack.isEmpty()) {
result = 1;
break;
}
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result *= currentOpStack.pop();
}
break;
case "/":
if (currentOpStack.isEmpty()) {
result = 1;
break;
}
result = currentOpStack.pop();
if (currentOpStack.isEmpty()) {
// Unary division
result = 1.0 / result;
break;
}
while(!currentOpStack.isEmpty()){
result /= currentOpStack.pop();
}
break;
case "+":
if (currentOpStack.isEmpty()) {
result = 0;
break;
}
result = currentOpStack.pop();
while(!currentOpStack.isEmpty()){
result += currentOpStack.pop();
}
break;
case "-":
if (currentOpStack.isEmpty()) {
result = 0;
break;
}
result = currentOpStack.pop();
if (currentOpStack.isEmpty()) {
// Unary minus
result = -result;
break;
}
while(!currentOpStack.isEmpty()){
result -= currentOpStack.pop();
}
break;
default:
result = currentOpStack.pop();
break;
}
Demo.