import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
/**
* A class that implements ICS 211 Homework 4, Infix Calculator. The infix
* calculator accepts input from a file specified as a command-line parameter.
* It reads each line of the file. For each line, it considers each character of
* the line, one at a time, taking the appropriate action for each character.
*
* @author Cheng Jade
* @assignment TA 4
* @date Feb 08, 2010
* @bugs None
*/
public class ChengJade04 {
/**
* Compares two operators. This method does not check to see if the precedence
* operators are valid.
*
* @param lhs The operator on the left hand side.
* @param rhs The operator on the right hand side.
* @return A value greater than zero if the operator on the left hand side is
* greater than the operator on the right hand side, a value less than
* zero if the operator on the right hand side is greater than the
* operator on the left hand side, or zero if the two operators have
* the same precedence.
*/
private static int compareOperator(final char lhs, final char rhs) {
// return the difference in the operator precedence values.
return getPrecedence(lhs) - getPrecedence(rhs);
}
/**
* Gets an integer value that represent's an operator's precedence. This
* method does not check to see if the precedence operator is valid.
*
* @param op The operator.
* @return An integer value that represent's the operator's precedence.
* Multiplication, division, and modulus have the same precedence
* values, and they are higher in precedence than addition and
* subtraction, which have the same precedence value.
*/
private static int getPrecedence(final char op) {
// return 1 for the add and minus operators.
if ("+-".indexOf(op) >= 0)
return 1;
// return 2 for multiply, divide, and modulus operators.
assert "*/%".indexOf(op) >= 0;
return 2;
}
/**
* Computes the result of an operation on two values. This method does not
* check to see if the operator is valid.
*
* @param lhs The value on the left hand side of the operator.
* @param op The operator.
* @param rhs The value on the right hand side of the operator.
* @return The result from the operator.
* @throws CalculatorException Thrown if there is division or modulus by zero.
*/
private static int compute(final int lhs, final char op, final int rhs)
throws CalculatorException {
// check for overflow while calculating the results.
if (op == '+')
return checkOverflow((long)lhs + (long)rhs);
if (op == '*')
return checkOverflow((long)lhs * (long)rhs);
if (op == '-')
return checkOverflow((long)lhs - (long)rhs);
// check for division by zero.
if (rhs == 0)
throw new CalculatorException("Division by zero.");
if (op == '/')
return checkOverflow((long)lhs / (long)rhs);
assert op == '%';
return checkOverflow((long)lhs % (long)rhs);
}
/**
* Pops two values off a number stack, computes the result based on the
* operator, and return the result. This method does not check to see if the
* operator is valid.
*
* @param numberStack The number stack.
* @param op The operator.
* @throws CalculatorException Thrown if there is division by zero or if the
* number stack is empty.
*/
private static void popComputePush(final Stack<Integer> numberStack,
final char op) throws CalculatorException {
// pop two values off the stack, compute the result, and return the result.
final int rhs = numberStack.pop();
final int lhs = numberStack.pop();
final int k = compute(lhs, op, rhs);
numberStack.push(k);
}
/**
* Evaluate if the operator stack and number stack are valid. The number
* stack should always have more or same number of elements versus the
* operator stack for a valid infix calculator expression.
*
* @param numberStack The number stack.
* @param operatorStack The operator stack.
*
* @return True if the stacks are valid or false if otherwise.
*/
private static boolean validStacks(Stack<Integer> numberStack, Stack<Character> operatorStack) {
return !(operatorStack.getSize() > numberStack.getSize());
}
/**
* This is the main entry point of the application.
*
* @param args The command line arguments. The user should specify a file with
* a list of lines to calculate.
*/
public static void main(final String[] args) {
// declare two stacks, one for the numbers, one for the operators.
final Stack<Integer> numberStack = new Stack<Integer>();
final Stack<Character> operatorStack = new Stack<Character>();
// check if only one file is passed in as the command line input.
if (args.length != 1) {
System.err.println("usage: ChengJade04 <path>");
System.exit(1);
return;
}
try {
// declare a FileReader to read the input file and also declare a Scanner
// to read through the FileReader.
final FileReader reader = new FileReader(args[0]);
final Scanner scanner = new Scanner(reader);
// the scanner loops through the file while there are more lines to read.
while (scanner.hasNextLine()) {
// initialize a String for the next line of the file.
final String line = scanner.nextLine();
// ignore the line if it's a blank line.
if (line.length() == 0)
continue;
// check for exceptions here only to display the line that failed in the
// outer catch block.
try {
// loop through each line checking each character from left to right.
for (int i = 0; i < line.length(); i++) {
// at any state, the operator stack can't have more elements than the
// number stack for a valid infix calculator expression.
if (!validStacks(numberStack, operatorStack)) {
System.err.println("Invalid Infix Calculator.");
break;
}
final char c = line.charAt(i);
// if it's a number, push it into the number stack.
if (Character.isDigit(c)) {
numberStack.push(c - '0');
continue;
}
// if it's a space, ignore it and move on to the next character.
if (Character.isSpaceChar(c))
continue;
// check for an invalid character.
if ("+-*/%".indexOf(c) < 0)
throw new Exception("Invalid character: '" + c + "'");
// loop until the operator stack is empty or if the new operator is
// greater than the top operator.
while (!operatorStack.empty()) {
// check if the top operator is less than or equal to the new
// operator in precedence.
final char topOperator = operatorStack.pop();
if (compareOperator(c, topOperator) > 0) {
// in this case push the operator back onto the stack and stop
// looping
operatorStack.push(topOperator);
break;
}
// pop two numbers off the stack, compute their values, and
// repeat.
popComputePush(numberStack, topOperator);
}
// push the new operator onto the stack.
operatorStack.push(c);
}
// now that end of the line was reached, loop until there are no more
// operators on the stack.
while (!operatorStack.empty()) {
// pop two numbers off the stack, compute their values, and repeat.
final char topOperator = operatorStack.pop();
popComputePush(numberStack, topOperator);
}
// check that there is only one left value on the stack.
if (numberStack.getSize() != 1)
throw new CalculatorException("Not enough operators.");
// display the line and the result.
final int result = numberStack.pop();
System.out.println("'" + line + "' = " + result);
} catch (final Exception e) {
// rethrow the exception to display the line that caused the failure.
throw new CalculatorException("Error on line '" + line + "': "
+ e.getMessage(), e);
}
}
} catch (final Exception e) {
// in case of any errors, display the message, and exit with a failure.
System.err.println(e.getMessage());
System.exit(1);
return;
}
// return zero to let the eclipse debugger close happily
System.exit(0);
}
/**
* Checks to see if the parameter (of type long) passed in is in the range of
* an integer type. If it is, the same value is returned casted back to an
* integer.
*
* @param n the number to be checked.
* @return The same value casted back to an integer.
* @throws CalculatorException Thrown if the value is not in the range of an
* integer type.
*/
private static int checkOverflow(final long n) throws CalculatorException {
// check for underflows.
if (n < Integer.MIN_VALUE)
throw new CalculatorException("Integer underflow encountered: " + n);
// check for overflows.
if (n > Integer.MAX_VALUE)
throw new CalculatorException("Integer overflow encountered: " + n);
// return the same value casted back as an integer type.
return (int)n;
}
}
/**
* A generic stack class.
*/
class Stack<T> {
/** An array to store the stack elements. */
private final ArrayList<T> array = new ArrayList<T>();
/**
* Pushes an item onto the stack.
*
* @param item the item to be pushed onto the stack.
*/
public void push(final T item) {
assert item != null;
array.add(item);
}
/**
* Pop an item off the top of the stack.
*
* @return the last item that was pushed onto the stack.
* @throws CalculatorException Thrown if the stack is empty.
*/
public T pop() throws CalculatorException {
// check the stack is not empty.
if (array.isEmpty())
throw new CalculatorException("The stack is empty.");
// remove the last item added to the stack and return it.
final int top = array.size() - 1;
final T result = array.get(top);
array.remove(top);
return result;
}
/**
* Returns true if the stack is empty.
*
* @return True if the stack is empty or false if the stack is not empty.
*/
public boolean empty() {
return array.isEmpty();
}
/**
* Returns the size of the stack.
*
* @return the number of items that can currently be popped off the stack.
*/
public int getSize() {
return array.size();
}
/**
* Returns the contents of the stack as a string.
*
* @return the contents of the stack as a string.
*/
@Override
public String toString() {
// return a special message if the stack is empty.
if (array.size() == 0)
return "The stack is empty.";
// build a list of items.
final StringBuilder builder = new StringBuilder();
builder.append("{ ");
for (int i = 0; i < array.size(); i++)
builder.append(array.get(i) + " ");
builder.append("}");
// return the list of items that looks like "{ a b c ... }".
return builder.toString();
}
}
/**
* An exception class that is thrown and caught by the program.
*/
@SuppressWarnings("serial")
class CalculatorException extends Exception {
/**
* Initializes a new instance of the class.
*
* @param message The message.
*/
public CalculatorException(final String message) {
super(message);
}
/**
* Initializes a new instance of the class.
*
* @param message The message.
* @param throwable The object that caused the exception.
*/
public CalculatorException(final String message, final Throwable throwable) {
super(message, throwable);
}
}
