For example:
(a+[b-{c*(d-e)}]+f) is correctly bracketed but (a+[b-{c*(d-e)]}+f) is not correctly bracketed.

Solution:
This is the case if
(a) There are the same number of left and right bracketes of each kinds,and
(b) When a right bracket appears,the most recent preceeding unmatched left bracket should be of the same type.
This can be decided by using stack. The expression is scanned left to right. When a left bracket is encountered,it is pushed onto the stack. When a right bracket is encountered, the stack is poped (if the stack is empty ,there are too many right brackets) and the brackets are compared. If they are of the same type,the scanning continues.If there is a mismatch,the expression is incorrectly bracketed. At the end of the expression ,if the stack is empty ,the expression is correctly bracketed otherwise there are too many left brackets.
[code]
.model small
.stack 100h
.data

cr equ 0DH ; cr represents carriage return
lf equ 0AH ; lf represents line feed

msg DB cr,lf,’ENTER AN ALGEBRIC EXPRESSION : ‘,cr,lf,’$’
msg_correct DB cr,lf,’EXPRESSION IS CORRECT.$’
msg_left_bracket DB cr,lf,’TOO MANY LEFT BRACKETS. BEGIN AGAIN!’,cr,lf,’$’
msg_right_bracket DB cr,lf,’TOO MANY RIGHT BRACKETS. BEGIN AGAIN!’,cr,lf,’$’
msg_mismatch DB cr,lf,’BRACKET MISMATCH. BEGIN AGAIN!’,cr,lf,’$’
msg_continue DB cr,lf,’Type Y if you want to Continue : ‘,cr,lf,’$’

.code

main proc

mov ax,@data ;get data segment
mov ds,ax ;initialising

start:
lea dx,msg ;user prompt
mov ah,9
int 21h

xor cx,cx ;initializing cx
mov ah,1

input: ;this label for taking input

int 21h

cmp al,0Dh ;checking if the enter is pressed or not
JE end_input

;if left bracket,then push on stack
cmp al, "["
JE push_data
cmp al, "{"
JE push_data
cmp al, "("
JE push_data

;if right bracket,then pop stack

cmp al, ")"
JE parentheses
cmp al, "}"
JE curly_braces
cmp al, "]"
JE line_bracket
jmp input

push_data:
push ax
inc cx
jmp input

parentheses:
dec cx
cmp cx,0
JL many_right

pop dx
cmp dl, "("
JNE mismatch
JMP input

curly_braces:
dec cx
cmp cx,0
JL many_right
pop dx
cmp dl, "{"
JNE mismatch
JMP input

line_bracket:
dec cx
cmp cx, 0
JL many_right
pop dx
cmp dl, "["
JNE mismatch
JMP input

end_input:
cmp cx, 0
JNE many_left

mov ah, 9
lea dx, msg_correct
int 21h

lea dx, msg_continue
int 21h

mov ah,1
int 21h

cmp al, "Y"
JNE exit
JMP start

mismatch:
lea dx, msg_mismatch
mov ah,9
int 21h
JMP start

many_left:
lea dx, msg_left_bracket
mov ah,9
int 21h
JMP start

many_right:
lea dx, msg_right_bracket
mov ah,9
int 21h
JMP start

exit:
mov ah,4ch
int 21h

MAIN ENDP
END MAIN
[/code]

Difficulties & Discussion:
Since I have already solved this problem in C, I hadn’t face too much problem for the algorithm to solve this in assembly language. All dificulties I faced was in the syntax of Assembly language. At first,finishing the code,it wasn’t working for some inputs like (a+b)) or (a+b)} for which output will be “TOO MANY RIGHT BRACKETS”. But my code was being redirected to starting position of main procedure because of my silly mistake.Thsi mistake was in line number 83,94 and 104.

Wrong code
[code] pop dx
dec cx
cmp cx,0
JL many_right
cmp dl, "{"
JNE mismatch
JMP input[/code]
Corrected code:
[code]
dec cx
cmp cx,0
JL many_right
pop dx
cmp dl, "{"
JNE mismatch
JMP input

[/code]

For the example (a+b)}
When the last ‘}’ is scanned,then stack is empty.but in the code I have poped from stack,which is an invalid instruction. But actually it is required that,I will first check if the stack is empty or not.If empty,then “too many right brackets”. If not then pop dx and should be checked with the scanned data.It was done in the right side code.

This problem is an application of stack implementation and we have successfully solved this using stack in assembly language.

শহীদ শাকিল নিহন
বিশিষ্ট কমপু প্রেমিক
————