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.
1#include <iostream>
2#include <stack>
3
4int calculate(std::string s) {
5 std::stack<int> stack;
6 char sign = '+';
7 int num = 0;
8 for (size_t i = 0; i < s.length(); ++i) {
9 if (isdigit(s[i])) {
10 num = num * 10 + (s[i] - '0');
11 }
12 if (!isdigit(s[i]) && !isspace(s[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 int top = stack.top();
19 stack.pop();
20 stack.push(top * num);
21 } else if (sign == '/') {
22 int top = stack.top();
23 stack.pop();
24 stack.push(top / num);
25 }
26 sign = s[i];
27 num = 0;
28 }
29 }
30
31 int result = 0;
32 while (!stack.empty()) {
33 result += stack.top();
34 stack.pop();
35 }
36 return result;
37}
38
39int main() {
40 std::string expression = "3+2*2";
41 std::cout << "Output: " << calculate(expression) << std::endl;
42 return 0;
43}This C++ solution utilizes the same logic with an std::stack to handle mutated values and precedence. It processes the input, modifies the stack during iterations, and sums the values at the end.
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 C code tracks the last number while parsing. It processes multiplication and division without using an additional stack by altering the last number, collects results using '+' and '-', and accumulates a final result.