สมมติว่าเรามีสตริง s เป็น S-expression เราต้องประเมินว่านิพจน์ S และส่งคืนผลลัพธ์เป็นจำนวนเต็ม ดังที่เราทราบแล้วว่า s-expression เป็นนิพจน์ที่เป็นหนึ่งตัวเลข หรือนิพจน์แบบเรียกซ้ำที่อยู่ในวงเล็บ เช่น (+ (- 3 2) (* 3 3)) ซึ่งระบุ (3 - 2) + (3 * 3) =10. ตัวดำเนินการที่ถูกต้องคือ +, -, * และ /.
ดังนั้น หากอินพุตเป็น s ="(- (+ 3 2) 2)" ผลลัพธ์จะเป็น 3 เนื่องจาก ((3 + 2) - 2) =3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
stack :=สแต็คใหม่
-
ลบวงเล็บเปิดและปิดของ s
-
a :=แบ่ง s โดยใช้ช่องว่างและสร้างรายการพาร์ติชั่น
-
สำหรับแต่ละ i ในลำดับที่กลับกัน ทำ
-
ถ้าขนาด i> 1 แล้ว
-
ถ้า i[0] เหมือนกับ "-" แล้ว
-
ดัน i เป็นจำนวนเต็มลงใน stack
-
ไปทำซ้ำต่อไป
-
-
มิฉะนั้น
-
ดัน i เป็นจำนวนเต็มลงใน stack
-
-
-
มิฉะนั้นเมื่อฉันเป็นตัวเลขแล้ว
-
ดัน i เป็นจำนวนเต็มลงใน stack
-
-
มิฉะนั้น
-
ถ้าขนาดของ stack>=2 แล้ว
-
num1 :=ป๊อปจากสแต็ก
-
num2 :=ป๊อปจากสแต็ก
-
ถ้าฉันเหมือนกับ "+" แล้ว
-
ดำเนินการ num1 + num2 แล้วดันเข้าไปในสแต็ก
-
-
มิฉะนั้นเมื่อฉันเหมือนกับ "-" แล้ว
-
ดำเนินการ num1 - num2 และผลักเข้าสู่สแต็ก
-
-
มิฉะนั้นเมื่อฉันเหมือนกับ "*" แล้ว
-
ดำเนินการ num1 * num2 และกดลงในสแต็ก
-
-
มิฉะนั้น
-
ดำเนินการ num1 / num2 และผลักเข้าสู่สแต็ก
-
-
-
-
-
ส่งคืนองค์ประกอบบนสุดจากสแต็ก และลบองค์ประกอบบนสุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution:
def solve(self, s):
stack = list()
s = s.replace("(", "")
s = s.replace(")", "")
a = s.split()
for i in a[::-1]:
if len(i) > 1:
if i[0] == "-":
stack.append(int(i))
continue
else:
stack.append(int(i))
elif i.isdigit():
stack.append(int(i))
else:
if len(stack) >= 2:
num1 = stack.pop()
num2 = stack.pop()
if i == "+":
stack.append(int(num1 + num2))
elif i == "-":
stack.append(int(num1 - num2))
elif i == "*":
stack.append(int(num1 * num2))
else:
stack.append(int(num1 / num2))
return stack.pop()
ob = Solution()
s = "(- (+ 3 2) 2)"
print(ob.solve(s)) อินพุต
s = "(- (+ 3 2) 2)"
ผลลัพธ์
3
