สมมติว่าเราต้องการสร้างเครื่องคิดเลขพื้นฐานหนึ่งเครื่องที่จะหาผลลัพธ์ของนิพจน์พื้นฐาน นิพจน์สามารถใส่วงเล็บเปิดและปิด บวกหรือลบสัญลักษณ์และช่องว่าง
ดังนั้นหากสตริงเป็นแบบ “5 + 2 - 3” ผลลัพธ์จะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0, sign :=1, num :=0, n :=size of s
-
กำหนดหนึ่งสแต็ก st
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
กำหนดอาร์เรย์ x =s ขนาด i
-
ถ้า x>='0' และ x <='9' แล้ว
-
นัม =นัม * 10
-
num =num + (x - '0')
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '(' แล้ว −
-
ret =ret + (เครื่องหมาย * num)
-
ใส่ ret ลงใน st
-
ใส่เครื่องหมายลงใน st
-
ret :=0, sign :=1, num :=0
-
-
มิฉะนั้นเมื่อ x เหมือนกับ ')' ดังนั้น −
-
ret =ret + (เครื่องหมาย * num), เครื่องหมาย :=1, num :=0
-
ret =ret * องค์ประกอบด้านบนของ st
-
ลบรายการออกจาก st
-
ret =ret + องค์ประกอบด้านบนของ st
-
ลบรายการออกจาก st
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '+' แล้ว −
-
ret =ret + (เครื่องหมาย * num), เครื่องหมาย :=1, num :=0
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '-' แล้ว −
-
ret =ret + (เครื่องหมาย * num), เครื่องหมาย :=- 1, num :=0
-
-
-
ถ้า num ไม่ใช่ศูนย์ ดังนั้น
-
ret =ret + เครื่องหมาย * num
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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"));
} อินพุต
"5 + 2 - 3"
ผลลัพธ์
4
