Giả sử chúng ta muốn tạo một máy tính cơ bản để tìm kết quả biểu thức cơ bản. Biểu thức có thể chứa dấu ngoặc đơn mở và đóng, biểu tượng dấu cộng hoặc dấu trừ và khoảng trống.
Vì vậy, nếu chuỗi giống như "5 + 2 - 3", thì kết quả sẽ là 7
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=0, sign:=1, num:=0, n:=size of s
-
Xác định một ngăn xếp
-
để khởi tạo i:=0, khi i
-
Xác định một mảng x =s có kích thước i
-
nếu x> ='0' và x <='9' thì
-
num =num * 10
-
num =num + (x - '0')
-
-
Ngược lại khi x giống với '(' thì -
-
ret =ret + (dấu * num)
-
chèn ret vào st
-
chèn đăng nhập vào st
-
ret:=0, ký hiệu:=1, num:=0
-
-
Ngược lại khi x giống với ')' thì -
-
ret =ret + (dấu * num), dấu:=1, num:=0
-
ret =ret * phần tử trên cùng của st
-
xóa mục khỏi st
-
ret =ret + phần tử trên cùng của st
-
xóa mục khỏi st
-
-
Ngược lại khi x giống với '+' thì -
-
ret =ret + (dấu * num), dấu:=1, num:=0
-
-
Ngược lại khi x giống với '-' thì -
-
ret =ret + (dấu * num), dấu:=- 1, num:=0
-
-
-
nếu num khác 0 thì
-
ret =ret + dấu * num
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calculate(string s) {
int ret = 0;
int sign = 1;
int num = 0;
int n = s.size();
stack <int> st;
for(int i = 0; i < n; ++i){
char x = s[i];
if(x >= '0' && x <= '9'){
num *= 10;
num += (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;
}
};
main(){
Solution ob;
cout << (ob.calculate("5 + 2 - 3"));
} Đầu vào
"5 + 2 - 3"
Đầu ra
4