สมมติว่าเรามีสตริงที่แสดงนิพจน์ ternary ที่ซ้อนกันตามอำเภอใจ เราต้องคำนวณผลลัพธ์ของนิพจน์ เราสามารถสรุปได้ว่านิพจน์ที่ให้มานั้นถูกต้องและประกอบด้วยตัวเลข 0-9 เท่านั้น ?, :, T และ F อักขระสองสามตัวเหล่านี้ (ในที่นี้ T และ F แทน True และ False ตามลำดับ) มีคุณสมบัติบางอย่าง -
-
ความยาวของสตริงที่กำหนดต้องน้อยกว่าหรือเท่ากับ 10000
-
แต่ละหมายเลขจะมีเพียงตัวเลขเดียวเท่านั้น
-
กลุ่มนิพจน์เงื่อนไขจากขวาไปซ้าย
-
เงื่อนไขจะเป็น T หรือ F เสมอ ดังนั้นเงื่อนไขจะไม่เป็นตัวเลข
-
ผลลัพธ์ของนิพจน์จะประเมินเป็นตัวเลข 0-9, T หรือ F เสมอ
ตัวอย่างเช่น หากอินพุตเป็นเหมือน “F?1:T?4:5” ดังนั้นผลลัพธ์จะเป็น 4 เนื่องจากจะแยกวิเคราะห์นิพจน์ทางขวาสุด “T?4:5” จะส่งกลับ 4 แล้ว นิพจน์หลักจะเป็น “F?1:4” ดังนั้นค่าที่ส่งคืนคือ 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=สตริงว่าง n :=ขนาดของ s สร้าง stack st
-
สำหรับฉันอยู่ในช่วง n – 1 ลงไปที่ 0
-
x :=s[i]
-
ถ้า st ไม่ว่างและด้านบนของ stack คือ '?' แล้ว
-
ลบออกจาก st
-
อันดับแรก :=ด้านบนของ st จากนั้นลบสององค์ประกอบออกจากสแต็ก
-
วินาที :=ด้านบนของสแต็กและลบออกจาก st
-
ถ้า x คือ T ให้ใส่ st ก่อน มิฉะนั้น ให้ใส่วินาทีลงใน st
-
-
มิฉะนั้น ให้ใส่ x ลงใน st
-
-
ในขณะที่ st ไม่ว่างเปล่าแล้ว
-
ret :=ret + ด้านบนของ st และลบออกจาก st
-
-
ย้อนกลับและย้อนกลับ
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack <char> 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("F?1:T?4:5"));
} อินพุต
"F?1:T?4:5"
ผลลัพธ์
4
