Data Structures : Lecture 8

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Checking expressions)

Checking expressions using STACK 

Consider an example using the expression:

{(a + b) × (c + d) + (c × d)]}

Scan the expression from left to right. 

·         The first entry to be scanned is ‘{’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry to be scanned is ‘(’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry is ‘a’, which is an operand. Therefore, it is discarded.

·         The next entry is ‘+’, which is an operator. Therefore, it is discarded.

·         The next entry is ‘b’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘)’, which is a right parenthesis

·         POP the topmost entry from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘×’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘(’, which is a left parenthesis

·         Push it into the stack

·         The next entry to be scanned is ‘c’, which is an operand. Therefore it is discarded

·         The next entry to be scanned is ‘+’, which is an operator. Therefore it is discarded

·         The next entry to be scanned is ‘d’, which is an operand. Therefore it is discarded

·         The next entry to be scanned is ‘)’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘+’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘(’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry to be scanned is ‘c’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘×’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘d’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘)’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘]’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets

Since the brackets do not match,

it is an INVALID expression.