สมมติว่าเรามีนิพจน์ที่เก็บนิพจน์ไตรภาคไว้ เราต้องประเมินผลลัพธ์ของนิพจน์ รองรับค่าบางอย่างเช่น T และ F สำหรับ True และ False และ “?” และอักขระ “:” มีคุณสมบัติบางอย่าง:
- ความยาวของสตริงที่กำหนดต้องน้อยกว่าหรือเท่ากับ 10000
- กลุ่มนิพจน์เงื่อนไขจากขวาไปซ้าย
- เงื่อนไขจะเป็น T หรือ F เสมอ ดังนั้นเงื่อนไขนี้จะไม่เป็นตัวเลข
- ผลลัพธ์ของนิพจน์จะประเมินเป็น T หรือ F เสมอ
ตัวอย่างเช่น หากอินพุตเป็นแบบ “T ? ที ? F :T :T” ดังนั้นผลลัพธ์จะเป็น F.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- ret :=สตริงว่าง n :=ขนาดของ s
- สร้างสแต็ก st
- สำหรับ i ในช่วง n – 1 เหลือ 0
- x :=s[i]
- ถ้า st ไม่ว่างและด้านบนของสแต็กคือ '?' แล้ว
- ลบออกจาก st
- ก่อน :=ด้านบนของ st จากนั้นลบสององค์ประกอบออกจากสแต็ก
- วินาที :=ด้านบนของสแต็ก และลบออกจาก st
- ถ้า x เป็น T ให้ใส่ st ก่อน มิฉะนั้น ให้ใส่วินาทีลงใน st
- มิฉะนั้นให้ใส่ x ลงใน st
- ในขณะที่ st ไม่ว่างเปล่า แล้ว
- ret :=ret + ด้านบนของ st และลบออกจาก st
- ย้อนกลับและย้อนกลับ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
#include
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack st;
for(int i = n - 1; i >= 0; i--){
char x = s[i];
if(!st.empty() && st.top() == '?'){
st.pop();
char first = st.top();
st.pop();
st.pop();
char second = st.top();
st.pop();
if(x == 'T'){
st.push(first);
}
else st.push(second);
}
else{
st.push(x);
}
}
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("T?T?F:T:T"));
} อินพุต
" T?T?F:T:T"
ผลลัพธ์
F
