figure matching parentheses this defines function called square that will return the square of its argument lisp is notorious for using lots and lots of parentheses in both of these examplesparentheses must appear in balanced fashion balanced parentheses means that each opening symbol has corresponding closing symbol and the pairs of parentheses are properly nested consider the following correctly balanced strings of parentheses(()()()()(((()))(()((())())compare those with the followingwhich are not balanced((((((()())(()()((the ability to differentiate between parentheses that are correctly balanced and those that are unbalanced is an important part of recognizing many programming language structures the challenge then is to write an algorithm that will read string of parentheses from left to right and decide whether the symbols are balanced to solve this problem we need to make an important observation as you process symbols from left to rightthe most recent opening parenthesis must match the next closing symbol (see figure alsothe first opening symbol processed may have to wait until the very last symbol for its match closing symbols match opening symbols in the reverse order of their appearancethey match from the inside out this is clue that stacks can be used to solve the problem once you agree that stack is the appropriate data structure for keeping the parenthesesthe statement of the algorithm is straightforward starting with an empty stackprocess the parenthesis strings from left to right if symbol is an opening parenthesispush it on the stack as signal that corresponding closing symbol needs to appear later ifon the other handa symbol is closing parenthesispop the stack as long as it is possible to pop the stack to match every closing symbolthe parentheses remain balanced if at any time there is no opening symbol on the stack to match closing symbolthe string is not balanced prop basic data structures