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 <stdio.h>
2#include <stdlib.h>
3#include <ctype.h>
4
5int calculate(char *s) {
6 int length = strlen(s);
7 int stack[length];
8 int top = -1;
9 char sign = '+';
10 int num = 0;
11 for (int i = 0; i < length; i++) {
12 if (isdigit(s[i])) {
13 num = num * 10 + (s[i] - '0');
14 }
15 if ((!isdigit(s[i]) && !isspace(s[i])) || i == length - 1) {
16 if (sign == '+') {
17 stack[++top] = num;
18 } else if (sign == '-') {
19 stack[++top] = -num;
20 } else if (sign == '*') {
21 stack[top] *= num;
22 } else if (sign == '/') {
23 stack[top] /= num;
24 }
25 sign = s[i];
26 num = 0;
27 }
28 }
29
30 int result = 0;
31 while (top != -1) {
32 result += stack[top--];
33 }
34 return result;
35}
36
37int main() {
38 char expression[] = "3+2*2";
39 printf("Output: %d\n", calculate(expression));
40 return 0;
41}This C solution iterates over the string, calculates numeric values, updates the stack with results immediately for '*', '/', while '+' and '-' add or subtract the number to/from the stack respectively. Finally, calculates the sum of values 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#include <iostream>
2
int calculate(std::string s) {
int num = 0, lastNum = 0, result = 0;
char sign = '+';
size_t length = s.size();
for (size_t i = 0; i < length; ++i) {
if (isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
}
if (!isdigit(s[i]) && !isspace(s[i]) || i == length - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum *= num;
} else if (sign == '/') {
lastNum /= num;
}
sign = s[i];
num = 0;
}
}
result += lastNum;
return result;
}
int main() {
std::string expression = "3+2*2";
std::cout << "Output: " << calculate(expression) << std::endl;
return 0;
}This C++ solution optimizes stack usage by maintaining the last computation. Only the previous calculation result is stored, and numbers are accumulated as necessary. The final result is evaluated by adding the last computed number.