เครื่องคิดเลขพื้นฐานใน C++ (Basic Calculator)

ภาพรวมปัญหา

คำนวณนิพจน์ที่มี +, -, 括號, และ space

ตัวอย่าง

"5 + 2 - 3" → 4

วิธีแก้ปัญหา: Stack + Single Pass

• เก็บ ret (ผลรวมปัจจุบัน), sign (+1/-1), num (ตัวเลขกำลังอ่าน)
• เจอ '(': push ret, push sign, reset ret=0, sign=1, num=0
• เจอ ')': ret += sign×num, pop sign×ret, pop +ret
• เจอ '+/-': ret += sign×num, update sign, num=0
• ท้ายสุด: ret += sign×num

โค้ด 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 x = s[i];
            if (x >= '0' && x <= '9') { num = num*10 + (x-'0'); }
            else if (x == '(') { ret += sign*num; st.push(ret); st.push(sign); ret=0; sign=1; num=0; }
            else if (x == ')') { ret += sign*num; sign=1; num=0; ret *= st.top(); st.pop(); ret += st.top(); st.pop(); }
            else if (x == '+') { ret += sign*num; sign=1; num=0; }
            else if (x == '-') { ret += sign*num; sign=-1; num=0; }
        }
        if (num) ret += sign*num;
        return ret;
    }
};

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

ผลลัพธ์

4

การวิเคราะห์ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n) — stack สำหรับ括號