Dare2Solve
Given a string s
representing a basic mathematical expression containing non-negative integers and operators (+
, -
, *
, /
), implement a function to evaluate the expression and return its value. The expression is assumed to be well-formed, meaning it contains no parentheses and follows standard precedence rules for operators (*
and /
have higher precedence than +
and -
).
The problem can be solved by iterating through the string and processing each character. The idea is to maintain a running total using a stack to handle the operations according to their precedence. By pushing intermediate results onto the stack, we can ensure that multiplication and division operations are handled before addition and subtraction, without explicitly handling operator precedence.
Initialization: Start by initializing a stack to hold intermediate results, a variable num
to build the current number as you iterate through the string, and a variable prev_operator
to keep track of the last operator encountered.
Iteration: Loop through the string, character by character:
num
by appending the digit to the current number.num
according to the previous operator (+
, -
, *
, /
):
+
, push num
onto the stack.-
, push -num
onto the stack.*
, pop the last number from the stack, multiply it by num
, and push the result back onto the stack./
, pop the last number from the stack, divide it by num
, and push the truncated result back onto the stack.num
to 0
and update prev_operator
to the current character.Final Calculation: After the loop, sum all the numbers in the stack. This sum represents the final result of the expression.
O(n), where n
is the length of the string s
. The algorithm processes each character in the string once, performing constant-time operations for each character.
O(n), where n
is the number of elements pushed onto the stack. In the worst case, every number and intermediate result could be pushed onto the stack, leading to linear space usage.
class Solution {
public:
int calculate(string s) {
stack<int> st;
int num = 0;
char prevOperator = '+';
for (int i = 0; i <= s.length(); i++) {
char ch = (i < s.length()) ? s[i] : '\0';
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
}
if ((!isdigit(ch) && ch != ' ') || i == s.length()) {
if (prevOperator == '+') st.push(num);
if (prevOperator == '-') st.push(-num);
if (prevOperator == '*') {
int temp = st.top() * num;
st.pop();
st.push(temp);
}
if (prevOperator == '/') {
int temp = st.top() / num;
st.pop();
st.push(temp);
}
prevOperator = ch;
num = 0;
}
}
int result = 0;
while (!st.empty()) {
result += st.top();
st.pop();
}
return result;
}
};
// Usage Example
// int main() {
// Solution sol;
// string expression = "3+2*2";
// int result = sol.calculate(expression);
// cout << "Result: " << result << endl; // Output: 7
// return 0;
// }
class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
prev_operator = '+'
for i in range(len(s) + 1):
ch = s[i] if i < len(s) else '\0'
if ch.isdigit():
num = num * 10 + int(ch)
if not ch.isdigit() and ch != ' ' or i == len(s):
if prev_operator == '+':
stack.append(num)
if prev_operator == '-':
stack.append(-num)
if prev_operator == '*':
stack.append(stack.pop() * num)
if prev_operator == '/':
stack.append(int(stack.pop() / num))
prev_operator = ch
num = 0
return sum(stack)
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0;
char prevOperator = '+';
for (int i = 0; i <= s.length(); i++) {
char ch = (i < s.length()) ? s.charAt(i) : '\0';
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (!Character.isDigit(ch) && ch != ' ' || i == s.length()) {
if (prevOperator == '+') stack.push(num);
if (prevOperator == '-') stack.push(-num);
if (prevOperator == '*') stack.push(stack.pop() * num);
if (prevOperator == '/') stack.push(stack.pop() / num);
prevOperator = ch;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
}
var calculate = function (s) {
let num = '';
let prevOperator = '+';
const stack = [];
for (let i = 0; i <= s.length; i++) {
const ch = s[i];
if (ch >= '0' && ch <= '9') {
num += ch;
}
if ((ch < '0' || ch > '9') && ch !== ' ' || i === s.length) {
if (prevOperator === '+') stack.push(Number(num));
if (prevOperator === '-') stack.push(-Number(num));
if (prevOperator === '*') stack.push(stack.pop() * Number(num));
if (prevOperator === '/') stack.push(Math.trunc(stack.pop() / Number(num)));
prevOperator = ch;
num = '';
}
}
return stack.reduce((total, cur) => total + cur, 0);
};