# 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:**

- 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. - 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.

Advertisement

/* 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