Basic Calculator II: เครื่องคิดเลขพื้นฐาน (+, -, *, /) ใน Python

โจทย์

Implement Basic Calculator evaluate string expression ที่มี: non-negative integers, +, -, *, /, และ spaces การหารเป็น integer division (truncate toward zero)

ตัวอย่าง: "3+2*2" → 7, " 3/2 " → 1, " 3+5 / 2 " → 5

อัลกอริทึม: Stack + Single Pass (Operator Precedence)

จัดการ precedence: * และ / ก่อน + และ -

• Scan string 左→右
• เก็บ current_number และ last_operator
• เมื่อเจอ operator ใหม่ (หรือจบ string): ประมวลผล last_operator กับ current_number
• +: push +num
• -: push -num
• *: pop top, push top * num
• /: pop top, push int(top / num) (truncate toward zero)
• สุดท้าย: sum stack

การติดตั้ง (Python Implementation)

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'  # Initial operator (treat first number as +num)
        
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            
            # Process when: operator encountered OR end of string
            if ch in '+-*/' or i == len(s) - 1:
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                elif op == '/':
                    # Python // truncates toward -inf, need toward 0
                    top = stack.pop()
                    if top < 0:
                        stack.append(-(-top // num))
                    else:
                        stack.append(top // num)
                
                op = ch
                num = 0
        
        return sum(stack)

# ทดสอบ
ob = Solution()
print(ob.calculate("3+2*2"))        # 7
print(ob.calculate(" 3/2 "))        # 1
print(ob.calculate(" 3+5 / 2 "))    # 5
print(ob.calculate("14-3/2"))       # 13
print(ob.calculate("1+2*3-4/2"))    # 1+6-2=5
print(ob.calculate("-3+2"))         # -1 (handled by initial op='+')

Output

7
1
5
13
5
-1

การจัดการ Division Truncate Toward Zero

Python // truncates toward negative infinity (-3//2 = -2) แต่โจทย์ต้องการ toward zero (-3/2 = -1)

def trunc_div(a, b):
    """Integer division truncating toward zero"""
    if a * b < 0:  # Different signs
        return -(-a // b)
    return a // b

# หรือใช้ int(a/b) (float division แล้ว truncate)
# แต่ระวัง precision สำหรับ large numbers

Complexity

• Time: O(n) - Single pass
• Space: O(n) - Stack (worst case all + or -)

Extension: Basic Calculator III (with parentheses)

เพิ่ม recursion หรือ stack สำหรับ parentheses ใช้ Shunting Yard Algorithm หรือ Recursive Descent Parser

สรุป

Basic Calculator II ใช้ Stack จัดการ Operator Precedence: * และ / คำนวันทันที (pop คำนวณ push กลับ) + และ - เก็บไว้ใน stack (deferred) สุดท้าย sum ทั้ง stack

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ