JAVA Evaluating postfix expressions — unable to throw empty or invalid expressions

问题: I'm writing a program that will evaluate a postfix expression and print both the original expression and the result. But I want to account for the validity of the expressio...

问题:

I'm writing a program that will evaluate a postfix expression and print both the original expression and the result. But I want to account for the validity of the expression as well. For this, I've written two exception classes -- one for an empty collection and one for invalid postfix expressions. But my code is getting stuck somewhere; my output evaluates the first expression correctly, but then only prints the original postfix expressions after that. I believe the problem is perhaps coming from my PostfixEvaluator class (see below), where I attempt to check for the size of my stack in the evaluate method. When commented out, my postfix expressions evaluate (albeit without the exceptions being caught, but still, it's something).

My code and resulting output:

Postfix Tester:

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();
        }
   }
}

Postfix Evaluator:

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;
    }
}

My 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();
    }
}

My input file of expressions (for testing purposes, the final two should throw the two exceptions):

8 4 + 3 *
7 5 2 * +
3 1 + 4 2 - *
5 8 2 - +
5 8 - +
6 3 2 -

My actual output:

8 4 + 3 *
The result is: 36

7 5 2 * +

3 1 + 4 2 - *

5 8 2 - +

5 8 - +

6 3 2 -

Obviously, I was expecting the first four expressions to follow as the first one did, and the final two to display my exception messages, but I can't seem to figure out where I've gone wrong.


回答1:

You push the result to the evaluator stack.

You reuse the evaluator in the tester.

The evaluator is not clean when you start the second iteration in tester (the result of the previous expression is in the stack).

The easiest (and the correct) way to fix this is to change "return result;" to "return stack.pop();"

Next time use a debugger and step through your failing code. It's one of the most useful skills you can have in programming.

Asserting preconditions would help too. Check that stack is empty when you start evaluating an expression.


回答2:

The exceptions are thrown but since class PostfixTester is using e.getMessgage(), you won't see the error in the output. You should use, System.out.println(e.getMessage()) in order to print message. But even this change will print null. You need to catch exceptions in PostfixEvaluator.evaluate() method and throw again with the message.

  • 发表于 2018-08-31 17:39
  • 阅读 ( 298 )
  • 分类:sof

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除