8086汇编中如何检查栈空？求完善括号匹配算法实现方案

Hey there! Let's walk through implementing bracket matching for math expressions in 8086 assembly, plus dive into how to check if the stack is empty—since that's a critical piece of your puzzle.

First, let's translate your high-level algorithm into assembly-specific steps:

• Initialize an empty stack: In 8086, the stack is managed by the SS (Stack Segment) and SP (Stack Pointer) registers. To start with an empty stack, set SP to the bottom of your allocated stack space. For example, if your stack segment is set to a 64KB block, you might use:

  MOV AX, @STACK   ; Load stack segment address into AX
  MOV SS, AX       ; Set SS to the stack segment
  MOV SP, 0FFFEH   ; Initialize SP to the bottom of the stack (empty state)
  

• Read the string until the end: Use the SI register to point to the start of your input string. Loop through each character (load into AL with MOV AL, [SI]) until you hit the string terminator (like 0 or '$', depending on how you've formatted your input). Increment SI each iteration to move to the next character.
• Push opening brackets to the stack: If the current character in AL is '(', '[', or '{', use the PUSH instruction to store it on the stack:

  CMP AL, '('
  JE PUSH_BRACKET
  CMP AL, '['
  JE PUSH_BRACKET
  CMP AL, '{'
  JE PUSH_BRACKET
  ; ... handle other characters or move to closing bracket check
  PUSH_BRACKET:
  PUSH AL
  

• Handle closing brackets:
  1. First, check if the stack is empty (we'll cover this in detail below). If it is, you've got a mismatched closing bracket—jump to your error handling code (e.g., print an error message or set an error flag).
  2. If the stack isn't empty, pop the top character into a register like BL with POP BL.
  3. Verify the popped bracket matches the closing one:

     CMP AL, ')'
     JE CHECK_PAREN
     CMP AL, ']'
     JE CHECK_BRACKET
     CMP AL, '}'
     JE CHECK_BRACE
     ; ...
     CHECK_PAREN:
     CMP BL, '('
     JNE BRACKET_MISMATCH
     JMP CONTINUE_LOOP
     CHECK_BRACKET:
     CMP BL, '['
     JNE BRACKET_MISMATCH
     JMP CONTINUE_LOOP
     CHECK_BRACE:
     CMP BL, '{'
     JNE BRACKET_MISMATCH
     

• Final stack check: Once you've processed the entire string, check if the stack is empty again. If it's not, there are unmatched opening brackets—trigger an error.

The 8086 CPU's stack is a downward-growing structure: when you push data, SP decreases by 2 (for 16-bit values) or 1 (for 8-bit, though most stack operations use 16-bit). The stack is empty when SP is back at its initial value (the stack bottom you set during initialization).

Here are two reliable methods:

1. Compare SP to the Initial Stack Pointer Value #

This is the most efficient way, since it uses the CPU's built-in stack registers.

; Assume we initialized SP to 0FFFEH at startup
CHECK_EMPTY_STACK:
    CMP SP, 0FFFEH
    JE STACK_IS_EMPTY   ; Jump if stack is empty
    ; Stack has elements—proceed with pop or other operations
    RET
STACK_IS_EMPTY:
    ; Handle empty stack error here
    ; e.g., print "Mismatched closing bracket"
    RET

Just make sure you use the same initial SP value you set when initializing the stack.

2. Use an Explicit Stack Counter (Optional) #

If you prefer a more explicit approach, you can track the number of elements in the stack with a register or memory location:

• Initialize a counter (e.g., BX) to 0 when the stack is empty.
• Increment the counter every time you push a bracket (INC BX).
• Decrement it every time you pop (DEC BX).
• To check if the stack is empty, compare the counter to 0: CMP BX, 0—if equal, stack is empty.

This adds a bit of overhead, but can be helpful for debugging or if you need to track stack size for other purposes.

If you're running into issues, double-check:

• You're using the correct ASCII values for brackets (e.g., '(' is 28H, ')' is 29H, '[' is 5BH, ']' is 5DH, '{' is 7BH, '}' is 7DH).
• Your stack initialization is correct—make sure SS is set properly before modifying SP.
• Your string loop is correctly terminating (don't forget to check for the end character!).

内容的提问来源于stack exchange，提问作者Mert Karabulut