tailieunhanh - Ebook Data structures and problem solving using C++ (2nd edition): Part 2

(BQ) Part 2 book "Data structures and problem solving using C++" has contents: Stacks & compilers, utilities, simulation, graphs & paths, stacks & queues, linked lists, trees, binary search trees, hash tables, a priority queue - the binary heap, splay trees, merging priority queues, the disjoint set class. | Chapter 12 Stacks and Compilers Stacks are used extensively in compilers. In this chapter we present two simple components of a compiler: a balanced symbol checker and a simple calculator. We do so to show simple algorithms that use stacks and to show how the STL classes described in Chapter 7 are used. In this chapter, we show: how to use a stack to check for balanced symbols, how to use a state machine to parse symbols in a balanced symbol program, and how to use operator precedence parsing to evaluate infix expressions in a simple calculator program. Balanced-Symbol Checker As discussed in Section , compilers check your programs for syntax errors. Frequently, however, a lack of one symbol (such as a missing * / comment-ender or 1) causes the compiler to produce numerous lines of diagnostics without identifying the real error. A useful tool to help debug compiler error messages is a program that checks whether symbols are balanced. In other words, every { must correspond to a 1, every [ to a l , and so on. However, simply counting the numbers of each symbol is insufficient. For example, the sequence [ ( ) 1 is legal, but the sequence [ ( I ) is wrong. Basic Algorithm A stack is useful here because we know that when a closing symbol such as is seen, it matches the most recently seen unclosed ( . Therefore, by placing an opening symbol on a stack, we can easily determine whether a closing symbol makes sense. Specifically, we have the following algorithm. A stack can be used detect mismatched symbols. Stacks and Compilers I > Symbols: ( [ ( [ I >* [ ) ) * [ eof* Errors (indicated by *): (when expecting) (with no matching opening symbol [ unmatched at end of input Figure Stack operations in a balanced-symbol algorithm 1. Make an empty stack. 2. Read symbols until the end of the file. a. If the symbol is an opening symbol, push it onto the stack. b. If it is a closing symbol do the following. i. If the stack is empty, report