Mathematical Expression Evaluator

delta_frost 0 Tallied Votes 460 Views Share

The above code computes the value of a mathematical expression supplied at command line by using the concept of converting infix to postfix,then evaluating the postfix expression. Any comments are appreciated.

/**
No decimal or alphabetical inputs
Use # instead of ^ operator
Supply input as arguments without spaces
anuvab1911
*/

import java.util.regex.*;
import java.util.*;

class ExpEval{
	public static int priority(String k){
		switch(k){
			case "#":
				return 5;
			case "/":
				return 4;
			case "*":
				return 3;
			case "+":
				return 2;
			case "-":
				return 1;
		}
		return -1;
	}

	public static int eval(String a,String b,String op){
		switch(op){
			case "/":
				return (Integer.parseInt(a)/Integer.parseInt(b));
			case "*":
				return (Integer.parseInt(a)*Integer.parseInt(b));
			case "+":
				return (Integer.parseInt(a)+Integer.parseInt(b));
			case "-":
				return (Integer.parseInt(a)-Integer.parseInt(b));
			case "#":
				return ((int)Math.pow(Integer.parseInt(a),Integer.parseInt(b)));
		}
		return -1;
	}
	public static void main(String args[]){
		String input=args[0];
		StringTokenizer alpha=new StringTokenizer(input,"+-*/#()");
		StringTokenizer beta=new StringTokenizer(input,"1234567890");
		LinkedList<String> infix=new LinkedList<String>();
		while(alpha.hasMoreTokens()){
			String operand=alpha.nextToken();
			infix.add(operand);
			try{
				String operator=beta.nextToken();
				infix.add(operator);
			}
			catch(Exception ex){
				//System.out.println("Reached end of expression");
				break;
			}

		}
		ListIterator<String> gamma=infix.listIterator();
		/*while(gamma.hasNext()){
			System.out.println(gamma.next());
		}*/
		//System.out.println("====================");
		LinkedList<String> infixOrig=new LinkedList<String>();
		//gamma=infix.listIterator();
		//System.out.println(infix+"\n"+infixOrig);
		//The following splits any dual-operands into two
		while(gamma.hasNext()){
			String v=gamma.next();
			if(v.length()>1){
				try{
					int num=Integer.parseInt(v);
					infixOrig.add(v);
					//System.out.println(v);
				}
				catch(NumberFormatException ex){
					//System.out.println(v + " is an operand");
					//Split into two operands
					String a=v.substring(0,1),b=v.substring(1,2);
					System.out.println(a + " " + b);
					int curIndex=infix.indexOf(v);
					//System.out.println(infixOrig.get(curIndex));
					infixOrig.add(a);
					infixOrig.add(b);
				}
			}
			else{
				infixOrig.add(v);
				//System.out.println(v);
			}
		}
		/*System.out.println("===================");
		gamma=infixOrig.listIterator();
		while(gamma.hasNext()){
			System.out.println(gamma.next());
		}*/
		//Got the complete infix order,now convert to postfix
		Stack<String> tempStack=new Stack<String>();
		LinkedList<String> postfix=new LinkedList<String>();
		tempStack.push("(");
		infixOrig.add(")");
		gamma=infixOrig.listIterator();
		while(!tempStack.isEmpty()){
			String element=gamma.next();
			try{
				Integer.parseInt(element);
				postfix.add(element);	
			}
			catch(NumberFormatException ex){
				//An operator has been encountered
				if(element.equals("("))
					tempStack.push("(");
				else if(element.equals(")")){
					while(!tempStack.peek().equals("("))
						postfix.add(tempStack.pop());
					tempStack.pop();
				}	
				else{
					while(priority((String)tempStack.peek())>priority(element)){
						postfix.add(tempStack.pop());
					}
					tempStack.push(element);
				}
			}
		}
		/*System.out.println("========================PF======================");
		gamma=postfix.listIterator();
		while(gamma.hasNext()){
			System.out.println(gamma.next());
		}
		System.out.println("========================VAL======================");*/		
		postfix.add(")");
		gamma=postfix.listIterator();
		while(gamma.hasNext()){
			String element=gamma.next();
			//System.out.println("Element = " + element);
			try{
				int a=Integer.parseInt(element);
				tempStack.push(Integer.toString(a));
			}
			catch(NumberFormatException ex){
				//An operator has been encountered
				if(element.equals(")"))
					break;
				String a=tempStack.pop();
				String b=tempStack.pop();
				tempStack.push(Integer.toString(eval(b,a,element)));
			}
		}
		System.out.println("Final Value = " + tempStack.peek());
	}
}
bguild 163 Posting Whiz

This is how I like to implement a calculator. It's longer, but it gives you more flexibility for adding operators. I've included some extra operators to illustrate that. I've kept comments minimalistic for brevity, but I hope the idea is clear.

import java.util.*;

/** Evaluator for expressions of type V */
public final class ExpEval<V> {
    private enum Kind {
        OPERAND, OPERATOR
    }
    public static final class Usage {
        private static final Usage OPERAND = new Usage(Kind.OPERAND, 0);
        public static Usage operand() {
            return OPERAND;
        }
        public static Usage operator(int precidence) {
            return new Usage(Kind.OPERATOR, precidence);
        }
        private final Kind kind;
        private final int precedence;
        private Usage(Kind kind, int precedence) {
            this.kind = kind;
            this.precedence = precedence;
        }
        public int precedence() {
            return precedence;
        }
        public boolean isOperand() {
            return kind == Kind.OPERAND;
        }
    }
    /** Result of parsing part of a string */
    public static final class Parse<V> {
        public final V value;
        public final String remainder;
        public Parse(V value, String remainder) {
            this.value = value;
            this.remainder = remainder;
        }
    }
    /** Stage for operators and operands between parsing and evaluating.
     *  Operators wait as elements while needed operands are parsed. */
    public interface Element<V> {
        public Usage leftUsage();
        public Usage rightUsage();
        public V evaluate(List<V> operands);
    }
    /** A kind of token, containing the ability to parse that token into an Element.
     *  With no separation between parsing and tokenization, tokens can be very elaborate */
    public interface TokenType<V> {
        public Parse<Element<V>> parse(ExpEval<V> eval, Usage previous, String source);
    }
    public static abstract class Operand<V> implements TokenType<V> {
        @Override
        public Parse<Element<V>> parse(ExpEval<V> eval, Usage previous, String source) {
            if(previous.isOperand()) return null;
            final Parse<V> parse = parse(source);
            if(parse == null) return null;
            final Element<V> result = new Element<V>() {
                @Override
                public Usage leftUsage() {
                    return Usage.operand();
                }
                @Override
                public Usage rightUsage() {
                    return Usage.operand();
                }
                @Override
                public V evaluate(List<V> operands) {
                    return parse.value;
                }
                @Override
                public String toString() {
                    return parse.value.toString();
                }
            };
            return new Parse<Element<V>>(result, parse.remainder);
        }
        public abstract Parse<V> parse(String source);
    }
    public static abstract class Bracket<V> implements TokenType<V> {
        private final String open;
        private final String close;
        private final Usage left;
        private final Usage right;
        public Bracket(String open, String close) {
            this(Usage.operand(), open, close, Usage.operand());
        }
        public Bracket(Usage left, String open, String close, Usage right) {
            this.left = left;
            this.open = open;
            this.close = close;
            this.right = right;
        }
        @Override
        public final Parse<Element<V>> parse(ExpEval<V> expEval, Usage previous, String source) {
            if(previous.isOperand() == left.isOperand())
                return null;
            else if(source.startsWith(open)) {
                final Parse<V> parse = expEval.subEval(source.substring(open.length()));
                if(parse == null) return null;
                else if(!parse.remainder.startsWith(close))
                    return null;
                Element<V> result = new Element<V>() {
                    @Override
                    public Usage leftUsage() {
                        return left;
                    }
                    @Override
                    public Usage rightUsage() {
                        return right;
                    }
                    @Override
                    public V evaluate(List<V> operands) {
                        return Bracket.this.evaluate(parse.value, operands);
                    }
                    @Override
                    public String toString() {
                        return open + parse.value.toString() + close;
                    }
                };
                return new Parse<Element<V>>(result, parse.remainder.substring(close.length()));
            } else return null;
        }
        public abstract V evaluate(V innerValue, List<V> operands);
    }
    public static abstract class Operator<V> implements Element<V>, TokenType<V> {
        private final String name;
        private final Usage left;
        private final Usage right;
        /** Unary prefix operator */
        public Operator(String name, int rightPrecedence) {
            this(name, Usage.operand(), Usage.operator(rightPrecedence));
        }
        /** Binary infix operator.
            Precedence can be different on either side to allow for associativity */
        public Operator(String name, int leftPrecedence, int rightPrecedence) {
            this(name, Usage.operator(leftPrecedence), Usage.operator(rightPrecedence));
        }
        /** Other kinds of operators */
        public Operator(String name, Usage left, Usage right) {
            this.name = name;
            this.left = left;
            this.right = right;
        }
        @Override
        public final Usage leftUsage() {
            return left;
        }
        @Override
        public final Usage rightUsage() {
            return right;
        }
        @Override
        public final Parse<Element<V>> parse(ExpEval<V> eval, Usage previous, String source) {
            if(previous.isOperand() == left.isOperand())
                return null;
            else if(source.startsWith(name))
                return new Parse<Element<V>>(this, source.substring(name.length()));
            else return null;
        }
        @Override
        public String toString() {
            return name;
        }
    }
    private final List<TokenType<V>> tokenList;
    public ExpEval(List<TokenType<V>> tokens) {
        tokenList = tokens;
    }
    private Parse<Element<V>> next(Usage usage, String input) {
        for (TokenType<V> t : tokenList) {
            final Parse<Element<V>> result = t.parse(this, usage, input);
            if(result != null)
                return result;
        }
        return null;
    }
    public V eval(String expression) {
        Parse<V> parse = subEval(expression);
        if(parse.remainder.length() != 0) throw new IllegalArgumentException();
        return parse.value;
    }
    public Parse<V> subEval(String expression) {
        final Deque<Element<V>> operatorStack = new ArrayDeque<Element<V>>();
        final Deque<V> operandStack = new ArrayDeque<V>();
        Usage previousUsage = Usage.operator(Integer.MIN_VALUE);
        String remainder = expression;
        while (true) {
            Parse<Element<V>> parse = next(previousUsage, remainder.trim());
            if(parse == null) break;
            Element<V> element = parse.value;
            remainder = parse.remainder;
            previousUsage = element.rightUsage();
            updateStack(operatorStack, operandStack, element);
        }
        while (!operatorStack.isEmpty()) {
            operandStack.addFirst(eval(operatorStack.removeFirst(), operandStack));
        }
        if(operandStack.size() != 1) throw new IllegalArgumentException();
        return new Parse<V>(operandStack.getFirst(), remainder.trim());
    }
    /** Make stacks reflect the arrival of a new element */
    private void updateStack
        (Deque<Element<V>> operatorStack, Deque<V> operandStack, Element<V> element) {
        final Usage leftUsage = element.leftUsage();
        final Usage rightUsage = element.rightUsage();
        if(!leftUsage.isOperand()) {
            final int nextPrecedence = leftUsage.precedence();
            while (!operatorStack.isEmpty()) {
                Element<V> top = operatorStack.getFirst();
                // Assume left-associativity
                // Use (top.rightUsage().precedence() > nextPrecedence) to assume right-associativity
                if(top.rightUsage().precedence() >= nextPrecedence)
                    operandStack.addFirst(eval(operatorStack.removeFirst(), operandStack));
                else break;
            }
            if(rightUsage.isOperand()) {
                V operand = operandStack.removeFirst();
                operandStack.addFirst(element.evaluate(Arrays.asList(operand)));
            } else operatorStack.addFirst(element);
        } else {
            if(rightUsage.isOperand())
                operandStack.addFirst(element.evaluate(Collections.<V>emptyList()));
            else
                operatorStack.addFirst(element);
        }
    }
    private static <V> V eval(Element<V> element, Deque<V> operandStack) {
        List<V> args = new ArrayList<V>(2);
        // Assume !element.rightUsage().isOperand()
        args.add(operandStack.removeFirst());
        if(!element.leftUsage().isOperand())
            args.add(0, operandStack.removeFirst());
        return element.evaluate(args);
    }
    private static Parse<Integer> parseInt(String input) {
        int i = 0;
        int value = 0;
        while (i < input.length()) {
            char c = input.charAt(i);
            if(Character.isDigit(c)) {
                value = value * 10 + Character.digit(c, 10);
                i++;
            } else break;
        }
        if(i == 0) return null;
        else return new Parse<Integer>(value, input.substring(i));
    }
    /** Just for fun, a postfix operator for selecting decimal digits from a number */
    private static int selectDigit(int value, int index) {
        if(value < 0) value = -value;
        while(index > 0) {
            value /= 10;
            index --;
        }
        return value % 10;
    }
    @SuppressWarnings("unchecked")
    public static final TokenType<Integer>[] intCalculatorOps
        = (TokenType<Integer>[])new TokenType<?>[]{
        new Operand<Integer>() {
            @Override
            public Parse<Integer> parse(String input) {
                return parseInt(input);
            }
        },new Bracket<Integer>("(",")") {
            @Override
            public Integer evaluate(Integer innerValue, List<Integer> operands) {
                return innerValue;
            }
        },new Bracket<Integer>("|","|") {
            @Override
            public Integer evaluate(Integer innerValue, List<Integer> operands) {
                return Math.abs(innerValue);
            }
        },new Bracket<Integer>(Usage.operator(10),"[","]",Usage.operand()) { // e.g. "123[2]" = 1
            @Override
            public Integer evaluate(Integer innerValue, List<Integer> operands) {
                return selectDigit(operands.get(0), innerValue);
            }
        },new Operator<Integer>("+", 1, 1) {
            @Override
            public Integer evaluate(List<Integer> operands) {
                return operands.get(0) + operands.get(1);
            }
        },new Operator<Integer>("-", 1, 1) {
            @Override
            public Integer evaluate(List<Integer> operands) {
                return operands.get(0) - operands.get(1);
            }
        },new Operator<Integer>("-", 1) { // Unary negation operator
            @Override
            public Integer evaluate(List<Integer> operands) {
                return -operands.get(0);
            }
        },new Operator<Integer>("*", 2, 2) {
            @Override
            public Integer evaluate(List<Integer> operands) {
                return operands.get(0) * operands.get(1);
            }
        },new Operator<Integer>("/", 2, 2) {
            @Override
            public Integer evaluate(List<Integer> operands) {
                return operands.get(0) / operands.get(1);
            }
        },new Operator<Integer>("^", 4, 3) { // Right associative (higher precedence on left side)
            @Override
            public Integer evaluate(List<Integer> operands) {
                int exponent = operands.get(1);
                int base = operands.get(0);
                if(exponent < 0)
                    return 0;
                int result = 1;
                for (int i = 0; i < exponent; i++)
                    result *= base;
                return result;
            }
        }};
    public static void main(String... args) {
        ExpEval<Integer> evaluator = new ExpEval<Integer>(Arrays.asList(intCalculatorOps));
        String input = args[0];
        System.out.println(input);
        System.out.println(evaluator.eval(input));
    }
}
bguild 163 Posting Whiz

On line 55, catching Exception is not a safe way to exit a loop. You are ignoring an enormous number of exceptions that might somehow be thrown. nextToken throws a NoSuchElementException when it runs out of tokens. If you caught that, then perhaps just breaking out of the loop would be an appropriate action to take, but you're catching Exception which might theoretically be something other than NoSuchElementException caused by some entirely unrelated reason. Because RuntimeExceptions are unchecked, you can never be sure what strange thing might be thrown. If that happens, you'll never know; your program will just fail mysteriously.

It's also bad practice to use an exception for something that you expect to happen when you don't have to. StringTokenizer has the hasMoreTokens method so that it should never need to throw a NoSuchElementException.

delta_frost 0 Newbie Poster

Thanks for the reply.Yes it is not a good practice to catch all Exceptions in a single catch block.But the add operation won't throw any Exceptions here because the input is being checked unless ofcourse the user supplies some bogus input.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.