Máy tính cơ bản (Basic Calculator) trong C++

Tính giá trị biểu thức chứa số nguyên, +, -, dấu ngoặc () và khoảng trắng.

Ví dụ

"5 + 2 - 3" → 4.

"(1+(4+5+2)-3)+(6+8)" → 23.

Thuật toán: Stack + Duyệt 1 lần

• ret: kết quả tính toán của cấp độ hiện tại.
• sign: dấu của số tiếp theo (+1 hoặc -1).
• num: số đang đọc.
• stack: lưu ret và sign khi gặp (.

Xử lý ký tự

• Chữ số: num = num*10 + (c-'0').
• (: push ret, push sign, reset ret=0, sign=1, num=0.
• ): ret += sign*num, pop sign nhân với ret, pop ret cũ cộng vào.
• +/-: ret += sign*num, cập nhật sign, reset num=0.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int calculate(string s) {
        int ret = 0, sign = 1, num = 0, n = s.size();
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if (c == '(') {
                ret += sign * num;
                st.push(ret); st.push(sign);
                ret = 0; sign = 1; num = 0;
            } else if (c == ')') {
                ret += sign * num; sign = 1; num = 0;
                ret *= st.top(); st.pop();
                ret += st.top(); st.pop();
            } else if (c == '+') {
                ret += sign * num; sign = 1; num = 0;
            } else if (c == '-') {
                ret += sign * num; sign = -1; num = 0;
            }
        }
        if (num) ret += sign * num;
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.calculate("5 + 2 - 3");
    return 0;
}

Độ phức tạp

• Thời gian: O(n) — duyệt chuỗi 1 lần.
• Không gian: O(n) — stack depth tối đa = độ sâu ngoặc.

Input / Output

Input:  "5 + 2 - 3"
Output: 4