Evaluate String Expression Java | InFix Expression Evaluation Java

Evaluate an expression represented by a String
The expression can contain parentheses, you can assume parentheses are well-matched. For simplicity, you can assume only binary operations allowed are +, -, *, and /.
Infix Notation: Operators are written between the operands they operate on, e.g. 3 + 4.

Input: 100 * ( 2 + 12 )

Output: 1400

Algorithm:

  1. While there are still tokens to be read in,
    1.1 Get the next token.
    1.2 If the token is:
    1.2.1 A number: push it onto the value stack.
    1.2.2 A variable: get its value, and push onto the value stack.
    1.2.3 A left parenthesis: push it onto the operator stack.
    1.2.4 A right parenthesis:
    1 While the thing on top of the operator stack is not a
    left parenthesis,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
    2 Pop the left parenthesis from the operator stack, and discard it.
    1.2.5 An operator (call it thisOp):
    1 While the operator stack is not empty, and the top thing on the
    operator stack has the same or greater precedence as thisOp,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
    2 Push thisOp onto the operator stack.
  2. While the operator stack is not empty,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
  • At this point the operator stack should be empty, and the value
    stack should have only one value in it, which is the final result.

  • /* A Java program to evaluate a given expression where tokens are separated by space.*/
    import java.util.Stack;
    
    public class EvaluateString
    {
    	public static int evaluate(String expression)
    	{
    		char[] tokens = expression.toCharArray();
    		String operators = "+-*/";
    
    		// Stack for numbers: 'values'
    		Stack<Integer> values = new Stack<Integer>();
    
    		// Stack for Operators: 'ops'
    		Stack<Character> ops = new Stack<Character>();
    		
    		for (int i = 0; i < tokens.length; i++)
    		{
    			// Current token is a whitespace, skip it
    			if (tokens[i] == ' ')
    				continue;
    
    			// Current token is a number,
    			// push it to stack for numbers
    			if (Character.isDigit(tokens[i]))
    			{
    				StringBuffer valueBuffer = new StringBuffer();
    				
    				// There may be more than one digits in number
    				while (i < tokens.length && Character.isDigit(tokens[i])) 
    					valueBuffer.append(tokens[i++]);
    				values.push(Integer.parseInt(valueBuffer.toString()));
    				// As we have move pointer ahead  we need to move it back once
    				i--;
    			}
    
    			// Current token is an opening brace, push it to 'ops'
    			else if (tokens[i] == '(')
    				ops.push(tokens[i]);
    
    			// Closing brace encountered, let's solve entire brace by poping out elements from ops and values till we get opening bracket
    			else if (tokens[i] == ')')
    			{
    				while (ops.peek() != '(')
    					values.push(applyOp(ops.pop(), values.pop(), values.pop()));
    				ops.pop();
    			}
    
    			// Current token is an operator.
    			else if (operators.indexOf(tokens[i])!=-1)
    			{
    				// While top of 'ops' has same or greater precedence to current token, which is an operator.
    				// Apply operator on top of 'ops' to top two elements in values stack
    				while (!ops.empty() && hasPrecedence(tokens[i], ops.peek())) 
    					values.push(applyOp(ops.pop(), values.pop(), values.pop()));
    				
    				// Push current token to 'ops'.
    				ops.push(tokens[i]);
    			}
    		}
    
    		// Entire expression has been parsed at this point, apply remaining ops to remaining values
    		while (!ops.empty())
    			values.push(applyOp(ops.pop(), values.pop(), values.pop()));
    
    		// Top of 'values' contains result, return it
    		return values.pop();
    	}
    
    	// Returns true if 'op2' has higher
    	// or same precedence as 'op1',
    	// otherwise returns false.
    	public static boolean hasPrecedence(
    						char op1, char op2)
    	{
    		if (op2 == '(' || op2 == ')')
    			return false;
    		if ((op1 == '*' || op1 == '/') &&
    			(op2 == '+' || op2 == '-'))
    			return false;
    	    return true;
    	}
    
    	// A utility method to apply an operator to operand a and b
    	public static int applyOp(char op, int b, int a)
    	{
    		switch (op)
    		{
    		case '+':
    			return a + b;
    		case '-':
    			return a - b;
    		case '*':
    			return a * b;
    		case '/':
    			if (b == 0)
    				throw new
    				UnsupportedOperationException(
    					"Cannot divide by zero");
    			return a / b;
    		}
    		return 0;
    	}
    
    	// Driver method to test above methods
    	public static void main(String[] args)
    	{
    		System.out.println(EvaluateString.
    						evaluate("10 + 2 * 6"));
    		System.out.println(EvaluateString.
    					evaluate("100 * 2 + 12"));
    		System.out.println(EvaluateString.
    				evaluate("100 * ( 2 + 12 )"));
    		System.out.println(EvaluateString.
    			evaluate("0 * ( 2 + 12 ) / 1"));
    	}
    }
    

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    four − three =

    Recent Posts

    Latest News