How to check balanced parentheses using emu8086

Question

To check prenthesis is balanced or not I coded this in c++ language but how can i convert this code into assembly emu8086 programme.

#include <iostream> //main header file
#include <stack>
using namespace std;
void balance_parentheses();
int main()
{
    int t;
    cout << "Enter number of test cases:";
    cin >> t;

    for (int i = 0; i < t; i++) {
        //calling of function for checking of brackets
        balance_parentheses();
    }    
    return 0;
}

void balance_parentheses()
{
    stack<char> a;
    string s;
    cout << "Enter string may or may not containing parentheses:";
    cin >> s;

    int flag = 0; //flag is an arbitrary variable

    for (int i = 0; i < s.length(); i++)
    //for length of the string calculated by number of letters
    {
        if (s[i] == '{' || s[i] == '[' || s[i] == '(') {
            //push function to enter terms in a stack
            a.push(s[i]);
            flag = 1;
        }
        if (!a.empty()) {
            if (s[i] == '}') {
                if (a.top() == '{')
                // top of the stack
                {
                    a.pop();
                    //pop function to delete terms from the top of array
                    continue;
                }
                else
                    break;
            }
            if (s[i] == ']') {
                if (a.top() == '[') {
                    a.pop();
                    continue;
                }
                else
                    break;
            }
            if (s[i] == ')') {
                if (a.top() == '(') {
                    a.pop();
                    continue;
                }
                else
                    break;
            }
        }
        else {
            break;
        }
    }

    if ((a.empty()) && (flag == 1))
        cout << "Balaned" << endl;
    else
        cout << "Not Balanced" << endl;
}

For simplicity, test input length is 8 fixed and after taking exactly 8 charachter, print the output.
for checking input (examples are given as):

[[]({})] ------ Balanced

{({}[])} ------ Balanced

[]({)}[] ------ Not Balanced

}()[(]){ ------ Not Balanced

score 0 · Accepted Answer · answered Jun 01 '21 at 07:13

Here at first, @ indicating start of label and $ indicating start of procedure. If multiple label and procedure is present in assembly code. Then distinguishing label & procedure can be done easily. It's just my own way of coding. You can ignore this style.

.model small               ; declaring this code will be consists of one data segment and one code segment
.stack 100h                ; stack is initializeed to offset address at 100h

.data                      ; Data segment

n_line db 0ah,0dh,"$"      ; for new line
msg1 db 10,13,"Balanced$" 
msg2 db 10,13,"Not Balanced$"

a1 dw 5bh ; '['
a2 dw 5dh ; ']'
b1 dw 7bh ; '{'
b2 dw 7dh ; '}'
c1 dw 28h ; '('
c2 dw 29h ; ')' 

flag db 0
i db ?  

.code                      ; Code segment

main proc
    mov ax,@data           ; copying starting address of data segment into ax register
    mov ds,ax              ; by copying ax into ds we are initializing data segment 
        
    mov cx,8               ; length is 8 fixed here    
    mov i,0d               ; https://stackoverflow.com/questions/45904075/displaying-numbers-with-dos
    xor ax,ax              ; clearing ax     
    xor bx,bx              ; clearing bx
    xor dx,dx              ; clearing dx
@input: 
    cmp i,8d
    jge @input_end
                                                  
        mov ah,1           ; taking input
        int 21h
        
        mov ah,0           ; clearing previously stored 1 in ah
        mov bp,sp          ; checking stack is empty or not using bp. it can be done sp in this code
        
        @if1:              ; in this @if1 level: checking if current input is opening bracket or not
           cmp ax,a1
           je @push_it
           cmp ax,b1
           je @push_it
           cmp ax,c1
           je @push_it
           
           jmp @if2
        @push_it:          ; if  current input is opening bracket then push it
            push ax 
            mov flag,1     ; and alter the default flag value
        
        @if2:
             cmp bp,100h   ; checking if stack is empty or not
             je @if2_end   ; if not empty then  
             
             @inner_if1:   ; in this @inner_if1 level, checking if top of the stack is co-responding closing bracket of '{' or not
                cmp ax,b2  ; top==}
                je @inner_if1_perform
                jne @inner_if2
                @inner_if1_perform:  
                    pop bx       ; top is popped and storing it to bx
                    cmp bx,b1
                    jne @inner_push1
                    je @inner_if2
                    
                    @inner_push1:
                        push bx   ; if not matched, then that popped value should be pushed
                  
              @inner_if2:   ; in this @inner_if2 level, checking if top of the stack is co-responding closing bracket of '[' or not
                 cmp ax,a2  ; top==]
                 je @inner_if2_perform
                 jne @inner_if3
                 @inner_if2_perform:
                    pop bx       ; top is popped and storing it to bx
                    cmp bx,a1
                    jne @inner_push2
                    je @inner_if3
                    
                    @inner_push2:
                        push bx   ; if not matched, then that popped value should be pushed
                 
              @inner_if3:   ; in this @inner_if3 level, checking if top of the stack is co-responding closing bracket of '(' or not
                 cmp ax,c2  ; top== )
                 je @inner_if3_perform
                 jne @inner_if3_end
                 @inner_if3_perform:
                    pop bx        ; top is popped and storing it to bx
                    cmp bx,c1
                    jne @inner_push3
                    je @inner_if3_end
                    
                    @inner_push3:
                        push bx    ; if not matched, then that popped value should be pushed
                        
               @inner_if3_end:                        
        @if2_end:
    inc i
    jmp @input   
    
@input_end:                ; if ( (flag == 1) && (stack.empty()) )
    cmp flag,1
    je @next_level:
    jne @print_msg2
    
    @next_level:          
    cmp sp,100h            ; cheking the stack pointer is returned to initial address or not means empty or not
    je @print_msg1
    jne @print_msg2                            

    @print_msg1:
        lea dx,msg1  
        mov ah,9
        int 21h 
@stop:     
    mov ah,4ch             ; terminate the code
    int 21h     
main endp                  ; ending of main procedure

@print_msg2:
    lea dx,msg2  
    mov ah,9
    int 21h  
    
    jmp @stop  
end main                   ; ending of code segment

;    Input:    
;    [[]({})] ------ Balanced
;    {({}[])} ------ Balanced
;    []({)}[] ------ Not Balanced
;    }()[(]){ ------ Not Balanced

`a1 dw 5bh ; '['` - normally you'd use `equ` to define a constant. The C++ program doesn't use `static int16_t a1 = '['` so there's no reason for you to use static storage in asm either. — Peter Cordes, Jun 01 '21 at 07:38
You could also make your branch conditions less noisy if you just wrote `jne @inner_if3` instead of using a `je @inner_if2_perform` with the same FLAGS to skip the `jne` if it wouldn't have been taken anyway. So the JNE is only even reached at all if it's going to be taken, and could have been a JMP. (But like I said, much better to remove the JE, and keep only the JNE, so it's either taken or falls through.) It never makes sense to have 2 branches in a row with opposite conditions (unless there's a branch target between them, if you could jump in from somewhere else with FLAGS set...) — Peter Cordes, Jun 01 '21 at 07:43
Checking for your stack data-structure being empty or not can be done without hard-coding absolute stack addresses, and without using `mov bp,sp` inside the loop. e.g. set up BP as a normal frame pointer, and compare. Also, right after pushing an open-paren, you might as well skip the checks to see which kind of close paren it might be. — Peter Cordes, Jun 01 '21 at 07:59
Your `mov cx,8` appears to be redundant. You never use CX or CL explicitly, or the `loop` instruction. Instead you count `i` (in memory for some reason) up toward 8. — Peter Cordes, Jun 01 '21 at 08:01
Overall, this seems like something that would best be posted to https://codereview.stackexchange.com/ where my comments could have been posted as an answer, not here as an example for others to follow. It's too messy for me to want to recommend it. (That's normal when you're still learning; in a few months or years you'll see the same problems if you look back on it.) I decided not to downvote, but I was leaning closer to that direction than an upvote. (The good comments, and the indenting, make it at least possible to follow the logic with a bit of work.) — Peter Cordes, Jun 01 '21 at 08:05

How to check balanced parentheses using emu8086

1 Answers1