Sponsored
Sponsored
This approach uses a stack to store numbers and consider operator precedence. Multiplication and division are processed immediately, whereas addition and subtraction modify how numbers are pushed onto the stack.
Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack.
1import java.util.Stack;
2
3public class BasicCalculatorII {
4 public static int calculate(String s) {
5 Stack<Integer> stack = new Stack<>();
6 char sign = '+';
7 int num = 0;
8 for (int i = 0; i < s.length(); i++) {
9 if (Character.isDigit(s.charAt(i))) {
10 num = num * 10 + (s.charAt(i) - '0');
11 }
12 if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1) {
13 if (sign == '+') {
14 stack.push(num);
15 } else if (sign == '-') {
16 stack.push(-num);
17 } else if (sign == '*') {
18 stack.push(stack.pop() * num);
19 } else if (sign == '/') {
20 stack.push(stack.pop() / num);
21 }
22 sign = s.charAt(i);
23 num = 0;
24 }
25 }
26 int result = 0;
27 while (!stack.isEmpty()) {
28 result += stack.pop();
29 }
30 return result;
31 }
32
33 public static void main(String[] args) {
34 System.out.println("Output: " + calculate("3+2*2"));
35 }
36}This Java solution parses the string, iterates over it to compute numeric values, updates the stack for multiplication and division immediately, handles addition and subtraction by pushing onto the stack, and finally sums all elements in the stack
This approach parses the expression twice, first to handle multiplications and divisions, then to process additions and subtractions. This avoids using a stack and simplifies sign handling.
Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types.
1
This Java solution focuses on efficiency by keeping track of only necessary information for computation: current number, last computed number, and current result. It simplifies calculations avoiding extra space usage.