Stack Implementation in Assembly Language (Algebric expression is correct or not.)

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.

অ্যাসেম্বলি ল্যাঙ্গুয়েজ় প্যানর প্যানর।

অ্যাসেম্বলি ল্যাঙ্গুয়েজ় একটা ভয়াবহ ল্যাঙ্গুয়েজ ,এইটার বই পরতে গিয়ে অনেকে এখনো শহীদ হয়েছে বলে লোকমুখে অনেক জনশ্রুতি আছে , সেই অজস্র বিদেহী আত্মার একজন হয়ে,অজস্র জীবিত আত্মাকে বাঁচানোর এক ক্ষুদ্র প্রয়াস আমার এই প্যানর প্যানর।
বাঙ্গালি নারীদের পরপুরুষে আসক্তি আছে কিনা,আমার বোঝার বয়স হই নাই ,তবে বাচ্চাকালে পরেছি ,ভারতের টোডা উপজাতির নারীদের একাধিক বর থাকে ,আমাদের সবার প্রেয়সী কম্পুবিবির ও আছে । ভারতের টোডা উপজাতির নারীদের শৌর্য-বীর্য প্রকাশ পায় একাধিক পুরুষ এর সাথে সাথে চলা ফেরায় ,কথা বার্তায় আর “হালুম-এ” । আমাদের কম্পুবিবিকে ও অনেকের সাথে অনেক ঢঙ্গে অনেক কথা বলতে হয়,অনেকের অনেক নীরব আকুতি সরবভাবে মেটাতে হয়।( প্যানর প্যানর বাদ দিয়ে আসল কথায় আসি ) কম্পুবিবি অজস্র আকুতি পূরণ করে একটা বিশেষ উপায়ে ।
তিনি কিছু সংখ্যা ছাড়া কিছুই বুঝেন না , তাহলে এত প্রেমিক পুরুষ কীভাবে ম্যানেজ করেন ,আর কীভাবে প্রেমের জোয়ারে বন্যা হয়ে যায় ? নারীশাসিত এই আধুনিক সমাজে পুরুষরা নারীর মন জুগিয়ে চলে (কারন পুরুষরা মহান!!) ,আর তাই নারীর যে ভাষা বুঝে ,তাদের কে পুরুষরা সে ভাষায় কবিতা শোনায় ,আর সে কবিতা পরে সংখ্যার মাধ্যমেই আদান প্রদান হয় ।
একটা উদাহারণ দেই তাহলে বুঝতে সুবিধা হবে । কেউ যদি কম্পিউটার কে কোন ভাবে বলে ১৪৩(বাইনারী তে বলতে হবে I LOVE YOU) তাহলে সে বুঝে নিবে যে তাকে যে কেউ ভালোবাসে । মানে কেউ বললো I LOVE YOU তখন সেইটা কে তো ১৪৩(বাইনারী) তে কনভার্ট করতে হবে ? এই কাজ করে “অ্যাসেম্বলার” । এর কাজ হচ্ছে যে কোন কিছুকে machine code এ রূপান্তর করা আর কম্পিউটার machine code অনুযায়ী কাজ করে । তাহলে আমরা যদি কম্পিউটার কে কোন কিছু করতে বলি আমাদের জানতে হবে অ্যাসেম্বলি ল্যাঙ্গুয়েজ় । অ্যাসেম্বলার নামের একটা সফটওয়ার এই ভাষাকে রূপান্তর করবে machine code এ ,কম্পিউটার সেই machine code পরে পরে কাজ করবে । আমরা যারা সি এর প্রোগ্রাম করি ,তখন আমরা যা লিখি সেইটা কম্পাইলার প্রথমে অ্যাসেম্বলি ল্যাঙ্গুয়েজ় এ রূপান্তর করে তারপর machine code এ রূপান্তর করে ,সেইটা দিয়ে আমাদের কোডের কাজগুলো কম্পিউটার করে । আমার লেখার স্পীড অনেক কম , আস্তে আস্তে বাকীটা লিখবো ,আজ কে এতটুকুই ।

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