Giả sử chúng ta có một chuỗi biểu thức đơn giản và phải triển khai máy tính cơ bản để tính giá trị biểu thức đó. Chuỗi biểu thức có thể chứa ngoặc mở và đóng, dấu cộng + hoặc trừ -, số nguyên không âm và khoảng trống. Chuỗi biểu thức chỉ chứa số nguyên không âm, toán tử +, -, *, /, ngoặc mở/đóng và khoảng trống. Phép chia nguyên nên cắt bỏ về phía 0.
Vì vậy, nếu đầu vào là "6-4 / 2", đầu ra sẽ là 4
Để giải quyết, chúng ta sẽ làm theo các bước:
l1 := 0, l2 := 1
o1 := 1, o2 := 1
Định nghĩa một ngăn xếp st
n := kích thước s
Khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), làm:
x := s[i]
nếu x >= '0' và x <= '9', thì:
num := x - '0'
Khi (i + 1 < n và s[i + 1] >= '0' và s[i + 1] <= '9'), làm:
(tăng i lên 1)
num := (num * 10) + (s[i] - '0')
l2 := (nếu o2 giống 1, thì l2 * num, ngược lại l2 / num)
ngược lại khi x giống '(', thì:
Chèn l1 vào st, chèn o1 vào st
Chèn l2 vào st, chèn o2 vào st
l1 := 0, o2 := 1
o1 := 1, l2 := 1
ngược lại khi x giống ')', thì:
temp := l1 + o1 * l2
o2 := phần tử đỉnh st
Xóa phần tử từ st
l2 := phần tử đỉnh st
Xóa phần tử từ st
o1 := phần tử đỉnh st
Xóa phần tử từ st
l1 := phần tử đỉnh st
Xóa phần tử từ st
l2 := (nếu o2 giống 1, thì l2 * temp, ngược lại l2 / temp)
ngược lại khi x giống '*' hoặc x giống '/', thì:
o2 := (nếu x giống '*', thì 1, ngược lại -1)
ngược lại khi x giống '+' hoặc x giống '-', thì:
nếu x giống '-' và (i giống 0 hoặc (i - 1 >= 0 và s[i - 1] giống '(')), thì:
o1 := -1
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
l1 := l1 + o1 * l2
o1 := (nếu x giống '+', thì 1, ngược lại -1)
l2 := 1, o2 := 1
Trả về l1 + o1 * l2
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#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<lli> 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; } }; main(){ Solution ob; cout << (ob.calculate("(5+9*3)/8")); }Đầu vào
"(5+9*3)/8"
Đầu ra
4