JAVA 计算后缀表达式 -- 无法抛出空的或无效的表达式
JAVA Evaluating postfix expressions -- unable to throw empty or invalid expressions
我正在编写一个程序来计算后缀表达式并打印原始表达式和结果。但我也想说明表达式的有效性。为此，我编写了两个异常 classes -- 一个用于空集合，一个用于无效后缀表达式。但是我的代码卡在了某个地方；我的输出正确地评估了第一个表达式，但随后只打印了原始的后缀表达式。我认为问题可能出在我的 PostfixEvaluator class（见下文）中，我试图在 evaluate 方法中检查堆栈的大小。注释掉时，我的后缀表达式会求值（尽管没有捕获到异常，但仍然是这样）。
我的代码和结果输出：
后缀测试员：
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class PostfixTester
{
/**
* Reads and evaluates multiple postfix expressions.
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException{
String expression, again;
int result;
//Scanner in = new Scanner(System.in);
Scanner in = new Scanner(new File("test.txt"));
PostfixEvaluator evaluator = new PostfixEvaluator();
while(in.hasNext()){
expression = in.nextLine();
System.out.println(expression);
try{
result = evaluator.evaluate(expression);
System.out.println("The result is: " + result);
}
catch(EmptyCollectionException e){
e.getMessage();
}
catch(InvalidPostfixExpressionException e){
e.getMessage();
}
System.out.println();
}
}
}
后缀评估器：
import java.util.Stack;
import java.util.Scanner;
public class PostfixEvaluator
{
private final static char ADD = '+';
private final static char SUBTRACT = '-';
private final static char MULTIPLY = '*';
private final static char DIVIDE = '/';
private ArrayStack<Integer> stack;
/**
* Sets up this evalutor by creating a new stack.
*/
public PostfixEvaluator()
{
stack = new ArrayStack<Integer>();
}
/**
* Evaluates the specified postfix expression. If an operand is
* encountered, it is pushed onto the stack. If an operator is
* encountered, two operands are popped, the operation is
* evaluated, and the result is pushed onto the stack.
* @param expr string representation of a postfix expression
* @return value of the given expression
*/
public int evaluate(String expr)
{
int op1, op2, result = 0;
String token;
Scanner parser = new Scanner(expr);
while (parser.hasNext())
{
token = parser.next();
if (isOperator(token))
{
op2 = (stack.pop()).intValue();
op1 = (stack.pop()).intValue();
result = evaluateSingleOperator(token.charAt(0), op1, op2);
stack.push(new Integer(result));
}
else
stack.push(new Integer(Integer.parseInt(token)));
}
if(stack.size() != 1){
throw new InvalidPostfixExpressionException();
}
return result;
}
/**
* Determines if the specified token is an operator.
* @param token the token to be evaluated
* @return true if token is operator
*/
private boolean isOperator(String token)
{
return ( token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/") );
}
/**
* Peforms integer evaluation on a single expression consisting of
* the specified operator and operands.
* @param operation operation to be performed
* @param op1 the first operand
* @param op2 the second operand
* @return value of the expression
*/
private int evaluateSingleOperator(char operation, int op1, int op2)
{
int result = 0;
switch (operation)
{
case ADD:
result = op1 + op2;
break;
case SUBTRACT:
result = op1 - op2;
break;
case MULTIPLY:
result = op1 * op2;
break;
case DIVIDE:
result = op1 / op2;
}
return result;
}
}
我的 ArrayStack class:
import java.util.Arrays;
public class ArrayStack<T> implements StackADT<T>
{
private final static int DEFAULT_CAPACITY = 100;
private int top;
private T[] stack;
/**
* Creates an empty stack using the default capacity.
*/
public ArrayStack()
{
this(DEFAULT_CAPACITY);
}
/**
* Creates an empty stack using the specified capacity.
* @param initialCapacity the initial size of the array
*/
public ArrayStack(int initialCapacity)
{
top = 0;
stack = (T[])(new Object[initialCapacity]);
}
/**
* Adds the specified element to the top of this stack, expanding
* the capacity of the array if necessary.
* @param element generic element to be pushed onto stack
*/
public void push(T element)
{
if (size() == stack.length)
expandCapacity();
stack[top] = element;
top++;
}
/**
* Creates a new array to store the contents of this stack with
* twice the capacity of the old one.
*/
private void expandCapacity()
{
stack = Arrays.copyOf(stack, stack.length * 2);
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element removed from top of stack
* @throws EmptyCollectionException if stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
top--;
T result = stack[top];
stack[top] = null;
return result;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if stack is empty
*/
public T peek() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
return stack[top-1];
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if this stack is empty
*/
public boolean isEmpty()
{
// To be completed as a Programming Project
return top==0;
}
/**
* Returns the number of elements in this stack.
* @return the number of elements in the stack
*/
public int size()
{
// To be completed as a Programming Project
return top;
}
/**
* Returns a string representation of this stack.
* @return a string representation of the stack
*/
public String toString()
{
return stack.toString();
}
}
我的表达式输入文件（出于测试目的，最后两个应该抛出两个异常）：
8 4 + 3 *
7 5 2 * +
3 1 + 4 2 - *
5 8 2 - +
5 8 - +
6 3 2 -
我的实际输出：
8 4 + 3 *
The result is: 36
7 5 2 * +
3 1 + 4 2 - *
5 8 2 - +
5 8 - +
6 3 2 -
显然，我希望前四个表达式会像第一个那样出现，最后两个表达式会显示我的异常消息，但我似乎无法弄清楚哪里出错了。
您将结果推送到计算器堆栈。
您在测试器中重复使用评估器。
在测试器中开始第二次迭代时求值器不干净（前一个表达式的结果在堆栈中）。
解决此问题的最简单（也是正确）方法是将 "return result;" 更改为 "return stack.pop();"
下次使用调试器逐步检查失败的代码。这是您在编程中可以拥有的最有用的技能之一。
断言先决条件也会有所帮助。开始计算表达式时检查堆栈是否为空。
抛出异常，但由于 class PostfixTester 使用 e.getMessgage()，你不会看不到输出中的错误。
您应该使用 System.out.println(e.getMessage()) 来打印消息。但即使是这个改变也会打印 null。
您需要在 PostfixEvaluator.evaluate() 方法中捕获异常并再次抛出消息。
我正在编写一个程序来计算后缀表达式并打印原始表达式和结果。但我也想说明表达式的有效性。为此，我编写了两个异常 classes -- 一个用于空集合，一个用于无效后缀表达式。但是我的代码卡在了某个地方；我的输出正确地评估了第一个表达式，但随后只打印了原始的后缀表达式。我认为问题可能出在我的 PostfixEvaluator class（见下文）中，我试图在 evaluate 方法中检查堆栈的大小。注释掉时，我的后缀表达式会求值（尽管没有捕获到异常，但仍然是这样）。
我的代码和结果输出：
后缀测试员：
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class PostfixTester
{
/**
* Reads and evaluates multiple postfix expressions.
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException{
String expression, again;
int result;
//Scanner in = new Scanner(System.in);
Scanner in = new Scanner(new File("test.txt"));
PostfixEvaluator evaluator = new PostfixEvaluator();
while(in.hasNext()){
expression = in.nextLine();
System.out.println(expression);
try{
result = evaluator.evaluate(expression);
System.out.println("The result is: " + result);
}
catch(EmptyCollectionException e){
e.getMessage();
}
catch(InvalidPostfixExpressionException e){
e.getMessage();
}
System.out.println();
}
}
}
后缀评估器：
import java.util.Stack;
import java.util.Scanner;
public class PostfixEvaluator
{
private final static char ADD = '+';
private final static char SUBTRACT = '-';
private final static char MULTIPLY = '*';
private final static char DIVIDE = '/';
private ArrayStack<Integer> stack;
/**
* Sets up this evalutor by creating a new stack.
*/
public PostfixEvaluator()
{
stack = new ArrayStack<Integer>();
}
/**
* Evaluates the specified postfix expression. If an operand is
* encountered, it is pushed onto the stack. If an operator is
* encountered, two operands are popped, the operation is
* evaluated, and the result is pushed onto the stack.
* @param expr string representation of a postfix expression
* @return value of the given expression
*/
public int evaluate(String expr)
{
int op1, op2, result = 0;
String token;
Scanner parser = new Scanner(expr);
while (parser.hasNext())
{
token = parser.next();
if (isOperator(token))
{
op2 = (stack.pop()).intValue();
op1 = (stack.pop()).intValue();
result = evaluateSingleOperator(token.charAt(0), op1, op2);
stack.push(new Integer(result));
}
else
stack.push(new Integer(Integer.parseInt(token)));
}
if(stack.size() != 1){
throw new InvalidPostfixExpressionException();
}
return result;
}
/**
* Determines if the specified token is an operator.
* @param token the token to be evaluated
* @return true if token is operator
*/
private boolean isOperator(String token)
{
return ( token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/") );
}
/**
* Peforms integer evaluation on a single expression consisting of
* the specified operator and operands.
* @param operation operation to be performed
* @param op1 the first operand
* @param op2 the second operand
* @return value of the expression
*/
private int evaluateSingleOperator(char operation, int op1, int op2)
{
int result = 0;
switch (operation)
{
case ADD:
result = op1 + op2;
break;
case SUBTRACT:
result = op1 - op2;
break;
case MULTIPLY:
result = op1 * op2;
break;
case DIVIDE:
result = op1 / op2;
}
return result;
}
}
我的 ArrayStack class:
import java.util.Arrays;
public class ArrayStack<T> implements StackADT<T>
{
private final static int DEFAULT_CAPACITY = 100;
private int top;
private T[] stack;
/**
* Creates an empty stack using the default capacity.
*/
public ArrayStack()
{
this(DEFAULT_CAPACITY);
}
/**
* Creates an empty stack using the specified capacity.
* @param initialCapacity the initial size of the array
*/
public ArrayStack(int initialCapacity)
{
top = 0;
stack = (T[])(new Object[initialCapacity]);
}
/**
* Adds the specified element to the top of this stack, expanding
* the capacity of the array if necessary.
* @param element generic element to be pushed onto stack
*/
public void push(T element)
{
if (size() == stack.length)
expandCapacity();
stack[top] = element;
top++;
}
/**
* Creates a new array to store the contents of this stack with
* twice the capacity of the old one.
*/
private void expandCapacity()
{
stack = Arrays.copyOf(stack, stack.length * 2);
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element removed from top of stack
* @throws EmptyCollectionException if stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
top--;
T result = stack[top];
stack[top] = null;
return result;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if stack is empty
*/
public T peek() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
return stack[top-1];
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if this stack is empty
*/
public boolean isEmpty()
{
// To be completed as a Programming Project
return top==0;
}
/**
* Returns the number of elements in this stack.
* @return the number of elements in the stack
*/
public int size()
{
// To be completed as a Programming Project
return top;
}
/**
* Returns a string representation of this stack.
* @return a string representation of the stack
*/
public String toString()
{
return stack.toString();
}
}
我的表达式输入文件（出于测试目的，最后两个应该抛出两个异常）：
8 4 + 3 *
7 5 2 * +
3 1 + 4 2 - *
5 8 2 - +
5 8 - +
6 3 2 -
我的实际输出：
8 4 + 3 *
The result is: 36
7 5 2 * +
3 1 + 4 2 - *
5 8 2 - +
5 8 - +
6 3 2 -
显然，我希望前四个表达式会像第一个那样出现，最后两个表达式会显示我的异常消息，但我似乎无法弄清楚哪里出错了。
您将结果推送到计算器堆栈。
您在测试器中重复使用评估器。
在测试器中开始第二次迭代时求值器不干净（前一个表达式的结果在堆栈中）。
解决此问题的最简单（也是正确）方法是将 "return result;" 更改为 "return stack.pop();"
下次使用调试器逐步检查失败的代码。这是您在编程中可以拥有的最有用的技能之一。
断言先决条件也会有所帮助。开始计算表达式时检查堆栈是否为空。
抛出异常，但由于 class PostfixTester 使用 e.getMessgage()，你不会看不到输出中的错误。 您应该使用 System.out.println(e.getMessage()) 来打印消息。但即使是这个改变也会打印 null。 您需要在 PostfixEvaluator.evaluate() 方法中捕获异常并再次抛出消息。