This is a LeetCode challenge. If interested this is the associated URL: https://leetcode.com/problems/basic-calculator-ii/?tab=Description

The description of the challenge is short and sweet. This seems to be typical of LeetCode challenges.

Following is a set of screen captures of the console of the Eclipse IDE using the three sample test cases:

3+2*2

main <<< s ==> 3+2*2 <==

main <<< evaluates: 7

3/2

main <<< s ==> 3/2 <==

main <<< evaluates: 1

3+5 / 2

main <<< s ==> 3+5 / 2 <==

main <<< evaluates: 5

When I read the requirements I immediately thought of the Dijkstra’s two-stack algorithm to evaluate fully parenthesized arithmetic expressions. Tried applying it **but** the challenge does not include parenthesis. The issue was with the order of operations (i.e., multiply and divide). By addressing it the Java code worked and the solution was accepted.

Additional test cases:

3/2 + 3 / 2

2

10/2

5

10/1/2

5

100000000/1/2

50000000

1 + 5*8/2

21

100000000/1/2/3/4/5/6/7/8/9/10

27

3+5/ 2

5

3 + 5 / 2

5

9 – 4 *2

1

1 + 5 % 3

**exception**

I even included a test for operands not supported (i.e., mod). Please keep in mind that the requirements state “** You may assume that the given expression is always valid**”.

My solution and test code follows:

**import** java.util.Scanner;

**import** java.util.Stack;

**public** **class** Solution {

/**

* Calculate the value (evaluate) of the expression in the specified string.

*/

**static** **int** calculate(String s) {

Stack<Integer> numStack = **new** Stack<Integer>();

Stack<String> opStack = **new** Stack<String>();

// **** remove all spaces from string ****

s = s.replaceAll(” “, “”);

// **** extract numbers and operators from string ****

String digit = “”;

**for** (**int** i = 0; i < s.length(); i++) {

// **** extract current character (for ease of use) ****

String c = s.substring(i, i + 1);

// **** operands: + * – / ****

**if** (“+*-/”.contains(c)) {

// **** push digit into stack (if needed) ****

digit = *pushInt*(numStack, digit);

// **** perform multiplication or division operation (if needed) ****

*isMulDivOp*(numStack, opStack);

// **** push operand into stack ****

opStack.push(c);

}

// **** char is a digit ****

**else** **if** (“1234567890”.contains(c)) {

digit += c;

}

// **** unknown operator ****

**else** {

**throw** **new** UnsupportedOperationException(“calculate <<< unsupported c ==>” + c + “<==”);

}

}

// **** push digit into stack (if needed) ****

digit = *pushInt*(numStack, digit);

// **** perform multiplication or division operation (if needed) ****

*isMulDivOp*(numStack, opStack);

// **** evaluate the operations in the expression ****

**int** result = 0;

**while** (!opStack.isEmpty()) {

// **** get ready to evaluate ****

**int** first = numStack.pop();

**int** second = numStack.pop();

String op = opStack.pop();

// **** evaluate ****

**switch** (op) {

**case** “+”:

result = first + second;

**break**;

**case** “-“:

result = second – first;

**break**;

**default**:

**throw** **new** UnsupportedOperationException(“calculate <<< unsupported op ==>” + op + “<==”);

}

// **** push result into stack ****

numStack.push(result);

}

// **** ****

**return** numStack.pop();

}

/**

* Perform multiplication or division operation (if needed).

*/

**private** **static** **void** isMulDivOp(Stack<Integer> numStack, Stack<String> opStack) {

// **** check if top operand is: * or / ****

**if** (!opStack.isEmpty()) {

String op = opStack.peek();

**if** (op.equals(“*”) || op.equals(“/”)) {

op = opStack.pop();

**int** first = numStack.pop();

**int** second = numStack.pop();

**int** result = 0;

// **** evaluate operation ****

**if** (op.equals(“/”)) {

result = second / first;

} **else** {

result = second * first;

}

// **** push result into stack ****

numStack.push(result);

}

}

}

/**

* Push digit on stack (if needed).

*/

**private** **static** String pushInt(Stack<Integer> numStack, String digit) {

**if** (!digit.equals(“”)) {

**int** d = Integer.*parseInt*(digit);

digit = “”;

numStack.push(d);

}

**return** digit;

}

/**

* Test code

*/

**public** **static** **void** main(String[] args) {

// **** ****

Scanner sc = **new** Scanner(System.** in**);

// **** get string to evaluate ****

String s = sc.nextLine();

System.** out**.println(“main <<< s ==>” + s + “<==”);

// **** close scanner ****

sc.close();

// **** evaluate and display result ****

System.** out**.println(“main <<< evaluates: ” +

*calculate*(s));

}

}

As usual I like to write simple, documented and clean code. If you encounter performance issues you can always optimize it.

If you have comments or questions regarding this or any other post, please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: **@john_canessa**