Basic Calculator II

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

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.