Câu hỏi:

29/09/2024 258

Em hãy minh hoạ:

a) Kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi [2 * (4 + 3) - 5] bằng cách sử dụng ngăn xếp.

b) Chuyển biểu thức (1 - 4) * 2 + 7 sang dạng hậu tố bằng cách sử dụng ngăn xếp.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

a) Kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi [2 * (4 + 3) - 5] bằng cách sử dụng ngăn xếp.

Code như sau:

   stack = []

    for char in bieu_thuc:

        if char == '(':

           stack.append(char)

        elif char == ')':

            if not stack or stack[-1] != '(':

               return False

           stack.pop()

    return len(stack) == 0

bieu_thuc_x = "[2 * (4 + 3) - 5]"

if kiem_tra_hop_le_ngoac(bieu_thuc_x):

   print(f"Biểu thức {bieu_thuc_x} có dấu ngoặc hợp lệ.")

else:

   print(f"Biểu thức {bieu_thuc_x} có dấu ngoặc không hợp lệ.")

Kết quả: Biểu thức [2 * (4 + 3) - 5] có dấu ngoặc hợp lệ.

b) Chuyển biểu thức (1 - 4) * 2 + 7 sang dạng hậu tố bằng cách sử dụng ngăn xếp.

Code như sau:

    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

    stack = []

    output = []

    for char in bieu_thuc:

        if char.isdigit():

           output.append(char)

        elif char in precedence:

           while (stack and stack[-1] != '(' and

                  precedence[char] <= precedence.get(stack[-1], 0)):

               output.append(stack.pop())

           stack.append(char)

        elif char == '(':

           stack.append(char)

        elif char == ')':

           while stack and stack[-1] != '(':

               output.append(stack.pop())

           stack.pop()

    while stack:

       output.append(stack.pop())

    return ' '.join(output)

bieu_thuc_b = "(1 - 4) * 2 + 7"

bieu_thuc_hau_to = chuyen_sang_hau_to(bieu_thuc_y)

print(f"Biểu thức {bieu_thuc_b} sau khi chuyển sang dạng hậu tố là: {bieu_thuc_hau_to}")

Kết quả của đoạn mã trên sẽ là:

Biểu thức (1 - 4) * 2 + 7 sau khi chuyển sang dạng hậu tố là: 1 4 - 2 * 7 +

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Sử dụng hàm isOperator() để kiểm tra kí tự là toán tử, hàm getPriority() để xác định độ ưu tiên của toán tử, hàm inFixtoPostfix() để chuyển biểu thức dạng trung tố sang dạng hậu tố

Hàm kiểm tra kí tự có phải là toán tử hay không:

def isoperator (c):

return c in '+-*/^'

Hàm kiểm tra độ ưu tiên của toán tử:

def getPriority (op):

if op '+' or op ==

return 1

elif op ==

return 2

elif op:

else:

return 3

return 0

or op '/':

chuyển biểu thức dạng trung tổ sang dạng hậu tố:

#Hàm chuyển biểu thức trung tổ sang hậu tổ

def inFixtoPostfix(infix):

infix infix.replace('[', '(').replace('1', ')').replace('(', '(').

Replace (‘}’, ‘)’)

Lace('}', ')')

stack initStack()

postfix = ""

for c in infix:

if c =='':

continue

#Bỏ qua khoảng trắng

#Nếu kí tự là toán hạng, thêm vào chuỗi hậu tố

if c.isalpha() or c.isdigit():

postfix += c

#Nếu kí tự là '(', thêm vào stack

elif (':

push(stack, c)

#Nếu kí tự là ')'

elif c == ')': #Lấy ra khỏi stack và thêm vào postfix cho đến khi gặp ( while not isEmptyStack(stack) and top (stack) != '(':

postfix += pop(stack)

pop(stack)

elif isOperator (c): #Toán tử

if c != '^':

while not isEmptyStack(stack) and getPriority(c) <= getPriority(top(stack)): postfix + pop (stack)

postfix + pop(stack)

push(stack, c)

stack): áng tạo

while not isEmptyStack (stack):

postfix += pop(stack)

return postfix

infix = '2* (4 + 3) - 5'

postfix = inFixtoPostfix (infix)

print("Biểu thức hậu tố: " postfix)

infix = '2^2^3'

postfix = inFixtoPostfix(infix)

print("Biểu thức hậu tố: ", postfix)

Lời giải

1. Sử dụng lệnh inFix = inFix[:-1] để đảo ngược chuỗi biểu thức trung tố. Ví dụ, *(2 – 7/3) * (2/8 – 4)" được chuyển thành ")4–8/2(*)3/7–2(".

2. Thay thế các dấu đóng ngoặc thành dấu mở ngoặc và dấu mở ngoặc thành dấu đóng ngoặc trong chuỗi biểu thức đã đảo ngược trong bước 1.

Ví dụ, chuỗi ")4–8/2(*)3/7−2(" được chuyển thành "(4 – 8/2) * (3/7 – 2)".

3. Gọi hàm inFixtoPostfix() chuyển từ biểu thức dạng trung tố sang dạng hậu tố. 4. Đảo ngược chuỗi biểu thức kết quả của 3.

5. Kết thúc.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP