Problem description:
This is a problem in elementary algebra is to decide if a given algebric expression containing several kinds of brackets,such as [,],{,},(,), is correctly bracketed or not.
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.