数据结构：思想与方法-翁惠玉-第二章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * #includeiostream using namespace std; #include balance.h int main(int argc, const char **argv) { char filename[80]; balance *p; int result; try { if ( argc == 1 ) { cout 请输入文件名:; cin filename; p = new balance(filename); result = p-CheckBalance(); delete p; cout 共 result 个错 endl; return 0; } while(--argc ) { cout 检查文件 *++argv endl; p = new balance(*argv); result = p-CheckBalance(); delete p; cout 共 result 个错 endl; } } catch (noFile) {cout no such file endl;} return 0; } * 栈的应用 递归函数的非递归实现 符号平衡检查 表达式的计算 * 中缀式和后缀式 对于一个表达式a+b 前缀式：+ab 波兰式 中缀式：a+b 后缀式：ab+ 逆波兰式 * 后缀式的优点 可以不考虑运算符的优先级 例如：(a + b) * c / ( d - e) 后缀式为：a b + c * d e - / * 一个后缀式是如何工作的？ 初始化一个栈。 依次读入后缀式的操作数和运算符。 若读到的是操作数，则将其进栈。 若读到的是运算符，则将栈顶的两个操作数出栈，后弹出的操作数为被操作数，先弹出的为操作数，将得到的操作数完成运算符所规定的运算，并将结果进栈。 回到2的读入操作，继续。 当栈中只剩有一个操作数时，弹出该操作数，它就是表达式的值。 * 以表达式5*(7-2*3)+8/2为例，它的后缀式为5 7 2 3*-*8 2/+ 步骤 读剩的后缀式 栈中内容 步骤 读剩的后缀式 栈中内容 1 5 7 2 3*-*8 2/+ 10 /+ 5 8 2 2 7 2 3*-*8 2/+ 5 11 + 5 4 3 2 3*-*8 2/+ 5 7 12 9 4 3*-*8 2/+ 5 7 2 13 5 *-*8 2/+ 5 7 2 3 14 6 -*8 2/+ 5 7 6 15 7 *8 2/+ 5 1 16 8 8 2/+ 5 17 9 2/+ 5 8 18 * 中缀式转换为后缀式的算法 若读入的是操作数，立即输出。 若读入的是闭括号，则将栈中的运算符依次出栈，并将其放在操作数序列之后。出栈操作一直进行到遇到相应的开括号为止。将开括号出栈。 若读入的是开括号，则进栈。 若读入的是运算符，如果栈顶运算符优先级高，则栈顶运算符出栈；出栈操作一直要进行到栈顶运算符优先级低为止，然后将新读入的运算符进栈保存。 在读入操作结束时，将栈中所有的剩余运算符依次出栈，并放在操作数序列之后，直至栈空为止。 * 序号 读剩的表达式 栈 输出 1 ( 5 + 6 * ( 7 + 3 ) / 3 ) / 4 + 5 2 5 + 6 * ( 7 + 3 ) / 3 ) / 4 + 5 ( 3 + 6 * ( 7 + 3 ) / 3 ) / 4 + 5 ( 5 4 6 * ( 7 + 3 ) / 3 ) / 4 + 5 (+ 5 5 * ( 7 + 3 ) / 3 ) / 4 + 5 (+ 5 6 6 7 + 3 ) / 3 ) / 4 + 5 (+*( 5 6 7 + 3 ) / 3 ) / 4 + 5 (+*( 5 6 7 8 3 ) / 3 ) / 4 + 5 (+*(+ 5 6 7 9 ) / 3 ) / 4 + 5 (+*(+ 5 6 7 3 10 / 3 ) / 4 + 5 (+ 5 6 7 3