Evaluate String Expression Java | InFix Expression Evaluation Java

Advertisement

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.
  3. 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"));
	}
}
Advertisement
Advertisement

Leave a Reply

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

nineteen + fifteen =

Share on Social Media