Strings - Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2³¹, 2³¹ - 1].

You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Input: s = "3+2*2"
Output: 7

Input: s = "3/2"
Output: 1

Input: s = "3+5 / 2"
Output: 5

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.

Solution 1 - Using a stack and loop over digits and operands in input string

In this approach, we will use a Stack to store operands and when we see a operator +, -, *, or / apply the operation on the operands.

Implementation steps:

We will create two variables number to capture digits as we loop through string s, and sign to track the operator. We will initialize sign = '+', the reason we do this is because, say for example input string is "10-2*3+5/2" for number 10 in the beginning it wil default to + sign.
We will also create a Stack for tracking current operands as we will loop through input string.
Then, we will loop through characters of input string s:

If the character is digit 0 -9 :

Read the character and add it to the number, when adding a new character into number we need ensure that the position of the numebr is correct. We can do it as follows, multiply current numebr with 10 and add new digit, for example the number is "79", first we will read 7, then when adding we will do it as 7*10 + 9 that converts string "79" to integer 79. number = number *10 + (current - '0'); If you dont want to do it this way, you can keep appending the number as string and when it's needed to convert to integer, use Integer.parseInt method.

If the character is an operator or the ending character of input:

If the sign is +, then add the number to the stack.
If the sign is -, then add the -number to the stack.
If the sign is *, then take the last number from the stack and multiply with number and add the result to stack.
If the sign is /, then take the last number from the stack and divide by number and add the result to stack.
Once added to the stack, update the sign variable with current sign and reset the number.
Now the stack contains numbers after applying * and / operations from above steps, now we can simply loop over the stack and return the sum of the numbers.

Example:

Let's take an example s = "10-2*3+5/2"

First initialize the variables number = 0, sign = '+', and an empty Stack.

Then, loop through characters of input string:

1^st character is 1, we will append this to number number = number * 10 + ('1' -'0'), this will become number = 0*10 + 1-0 = 1.
2^nd character is 0, we will append this to number, it will become number = 1 *10 + 0-0 = 10.
3^rd character is an operator -, so we will check the current value that sign holding, which is +, so we add current number 10 to the stack and update sign = '-' and reset number = 0.

stack

10
4^th character is 2, so we will add it to number, it will become 2.
5^th character is an operator *, so we will check the current value that sign holding, which is -, so we add current number with - sign -2 to the stack and update sign = '*' and reset number = 0.

stack

-2

10
6^th character is 3, so we will add it to number, it will become 3.
7^th character is an operator +, so we will check the current value that sign holding, which is *, so we take latest from stack, multiply with current number, and add it back to stack. So, top number from stack is -2 and current number is 3, so we will add -6 to the stack and update sign = '+' and reset number = 0.

stack

-6

10
8^th character is 5, so we will add it to number, it will become 5.

stack
10

stack
-2
10

stack
-6
10

9^th character is an operator /, so we will check the current value that sign holding, which is +, so we will add 5 to the stack and update sign = '/' and reset number = 0. tr>

stack
5
-6
10

10^th character is the last character 2, so we take latest from stack, divide by current number, and add it back to stack. So, top number from stack is 5 and current number is 2, so we will add 5 /2 = 2 to the stack. tr>

stack
2
-6
10

Now, we will go through the stack and add them up, 2 - 6 + 10 = 6, that is our answer.

import java.util.Stack; public class BasicCalculatorII { static int calculate(String s) { Stack<Integer> stack = new Stack<>(); int number = 0; char sign = '+'; // reason we are using this is say if the input is "10-2*3+5/2" // assume + is default sign for 10, if the starting is -10 for example, then it will 0+ at the beginning. for(int i=0; i<s.length(); i++) { char current = s.charAt(i); if(Character.isDigit(current)) { // If the character is between 0-9 number = number *10 + (current - '0'); // number *10 is to concatenate the number, // say if the input is two digit letter, // for example, 79 first we take 7, then when we get 9 we have to move 7 to 10th position, // so we multiply with 10, then add current number. } if( (!Character.isDigit(current) && current != ' ') || i == s.length() -1 ) { if(sign == '+') { stack.push(number); } else if(sign == '-') { stack.push(-number); } else if (sign == '*') { stack.push(stack.pop() * number); } else if (sign == '/') { stack.push(stack.pop() / number); } sign = current; number = 0; } } int result = 0; while(!stack.isEmpty()) { result+=stack.pop(); } return result; } public static void main(String[] args) { System.out.println(calculate("3+5 / 2 ")); System.out.println(calculate("10-2*3+5/2")); System.out.println(calculate("-10-2*3+5/2")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(n) for the Stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Example:

Complexity Analysis: