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

สมมติว่าเรามีสตริงนิพจน์ง่ายๆ และเราต้อง implement เครื่องคิดเลขพื้นฐานเพื่อประเมินนิพจน์นั้น นิพจน์อาจมีวงเล็บเปิดปิด เครื่องหมายบวก + หรือลบ - จำนวนเต็มที่ไม่ใช่ลบ และช่องว่าง นิพจน์ประกอบด้วยจำนวนเต็มไม่ติดลบ, ตัวดำเนินการ +, -, *, /, วงเล็บเปิดปิด และช่องว่าว การหารจำนวนเต็มควร truncate ไปทางศูนย์

ดังนั้น หากอินพุทคือ "6-4/2" ผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• l1 := 0, l2 := 1

• o1 := 1, o2 := 1

• กำหนด stack st

• n := ขนาดของ s

• for i := 0 ถึง n-1:

  • x := s[i]

  • ถ้า x เป็นตัวเลข 0-9: อ่านตัวเลขเต็ม num, l2 := (o2==1) ? l2*num : l2/num

  • else if x == '(': push l1, o1, l2, o2 ลง stack; reset l1=0, o1=1, l2=1, o2=1

  • else if x == ')': temp := l1 + o1*l2; pop o2, l2, o1, l1 จาก stack; l2 := (o2==1) ? l2*temp : l2/temp

  • else if x == '*' หรือ '/': o2 := (x=='*') ? 1 : -1

  • else if x == '+' หรือ '-':

    • ถ้า x == '-' และ (i==0 หรือ s[i-1]=='('): o1 := -1; continue

    • l1 := l1 + o1*l2; o1 := (x=='+') ? 1 : -1; l2 := 1; o2 := 1

• คืนค่า l1 + o1*l2

ตัวอย่างโค้ด

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

typedef long long int lli;

class Solution {
public:
    int calculate(string s) {
        lli l1 = 0;
        lli l2 = 1;
        lli o1 = 1;
        lli o2 = 1;
        stack st;
        lli n = s.size();
        for (lli i = 0; i < n; i++) {
            char x = s[i];
            if (x >= '0' && x <= '9') {
                lli num = x - '0';
                while (i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9') {
                    i++;
                    num = (num * 10) + (s[i] - '0');
                }
                l2 = (o2 == 1) ? l2 * num : l2 / num;
            } else if (x == '(') {
                st.push(l1);
                st.push(o1);
                st.push(l2);
                st.push(o2);
                l1 = 0;
                o2 = 1;
                o1 = 1;
                l2 = 1;
            } else if (x == ')') {
                lli temp = l1 + o1 * l2;
                o2 = st.top(); st.pop();
                l2 = st.top(); st.pop();
                o1 = st.top(); st.pop();
                l1 = st.top(); st.pop();
                l2 = (o2 == 1) ? l2 * temp : l2 / temp;
            } else if (x == '*' || x == '/') {
                o2 = (x == '*') ? 1 : -1;
            } else if (x == '+' || x == '-') {
                if (x == '-' && (i == 0 || (i - 1 >= 0 && s[i - 1] == '('))) {
                    o1 = -1;
                    continue;
                }
                l1 += o1 * l2;
                o1 = (x == '+') ? 1 : -1;
                l2 = 1;
                o2 = 1;
            }
        }
        return l1 + o1 * l2;
    }
};

int main() {
    Solution ob;
    cout << (ob.calculate("(5+9*3)/8"));
    return 0;
}

อินพุต

"(5+9*3)/8"

เอาต์พุต

4