the sequence [()is legalbut [(]is wrong obviouslyit is not worthwhile writing huge program for thisbut it turns out that it is easy to check these things for simplicitywe will just check for balancing of parenthesesbracketsand braces and ignore any other character that appears the simple algorithm uses stack and is as followsmake an empty stack read characters until end of file if the character is an opening symbolpush it onto the stack if it is closing symbol and the stack is emptyreport an error otherwisepop the stack if the symbol popped is not the corresponding opening symbolthen report an error at end of fileif the stack is not emptyreport an error you should be able to convince yourself that this algorithm works it is clearly linear and actually makes only one pass through the input it is thus online and quite fast extra work can be done to attempt to decide what to do when an error is reported--such as identifying the likely cause postfix expressions suppose we have pocket calculator and would like to compute the cost of shopping trip to do sowe add list of numbers and multiply the result by this computes the purchase price of some items with local sales tax added if the items are and then natural way to enter this would be the sequence depending on the calculatorthis produces either the intended answer or the scientific answer most simple four-function calculators will give the first answerbut many advanced calculators know that multiplication has higher precedence than addition on the other handsome items are taxable and some are notso if only the first and last items were actually taxablethen the sequence would give the correct answer ( on scientific calculator and the wrong answer ( on simple calculator scientific calculator generally comes with parenthesesso we can always get the right answer by parenthesizingbut with simple calculator we need to remember intermediate results typical evaluation sequence for this example might be to multiply and saving this answer as we then add and saving the result in we multiply and saving the answer in and finish by adding and leaving the final answer in we can write this sequence of operations as follows this notation is known as postfixor reverse polish notationand is evaluated exactly as we have described above the easiest way to do this is to use stack when number is seenit is pushed onto the stackwhen an operator is seenthe operator is applied to the