ให้สตริงนิพจน์คณิตศาสตร์ประกอบด้วย +, -, *, / (หารจำนวนเต็ม) คำนวณผลลัพธ์โดยไม่ใช้ eval หรือฟังก์ชันสำเร็จรูป
ตัวอย่าง: "2+3*5/7" → 4 (เพราะ 2 + ((3*5)/7) = 2 + 2 = 4)
อัลกอริธึม Recursive Descent Parser
- กลับสตริงเพื่อประมวลผลจากซ้ายไปขวา
get_value(): อ่านตัวเลข (รองรับเครื่องหมายลบ)get_term(): จัดการ * และ / (precedence สูงกว่า)- ลูปหลัก: จัดการ + และ -
การนำไปใช้
from math import floor
class Solution:
def solve(self, s):
s = list(s[::-1])
def get_value():
sign = 1
if s and s[-1] == "-":
s.pop()
sign = -1
value = 0
while s and s[-1].isdigit():
value *= 10
value += int(s.pop())
return sign * value
def get_term():
term = get_value()
while s and s[-1] in "*/":
op = s.pop()
value = get_value()
if op == "*":
term *= value
else:
term = floor(1.0 * term / value)
return term
ans = get_term()
while s:
op, term = s.pop(), get_term()
if op == "+":
ans += term
else:
ans -= term
return ans
ob = Solution()
print(ob.solve("2+3*5/7")) # 4
