2015信息安全数据结构实验1.docVIP

实验二 栈的应用－括号匹配 一、实验目的 1、掌握STL中栈的基本使用 2、练习使用栈进行程序编写 二、实验内容 题目一：STL 下面代码使用STL中的栈进行序列的反转，请修改好下面代码中的语法错误，编译运行 #include stack int main( ) /* Pre: The user supplies an integer n and n decimal numbers. Post: The numbers are printed in reverse order. Uses: The STL class stack and its methods */ { int n; double item; stackdouble numbers; // declares and initializes a stack of numbers cout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. endl; cin n; for (int i = 0; i n; iCC) { cin item; numbers.push(item); } cout endl endl; while (!numbers.empty( )) { cout numbers.top( ) ; numbers.pop( ); } cout endl; } 提示： （1）由于程序是用了STL（标准模板库，可以简单的看成是一个函数库，在其中有各种有用的类、函数和算法），栈在其中有实现。栈在STL中的实现用到了类模板，也就是说其栈是独立于类型的，模板提供参数化类型，也就是能将类型名作为参数传递给接收方来建立类或函数。比如stackdouble numbers;中就是声明了一个栈，这个栈中存放的数据类型为double。 （2）要使用c++的输入输出需要加上几行语句如下，因为cout和cin是在命名空间std中的： #include iostream using namespace std; 题目二：括号匹配 使用STL中的栈编写程序，实现算术表达式中的括号匹配（有能力的同学可以同时进行小括号，大括号，中括号的匹配） 注意： （1）配对的算术表达式中左右括号的数目应相等 例如：表达式（a+b））和a+b）中的括号不配对 （2）对的算术表达式中每一个左括号都一定有一个右括号与之匹配，并且一定是先出现左括号，才能有右括号 例如：表达式）a+b（+c和（b+a））+（c+d也属于不配对的情况 算法提示： 方式是先创建一个存放左括号的空栈，并将“#”作为栈底元素。顺序扫描表达式，当遇到非括号时，继续扫描，遇到“（”时，进栈，而遇到“）”时，与栈顶元素比较，如果括号匹配，栈顶元素退栈，继续扫描表达式，否则，报错退出。 括号配对检查的原则是：对表达式从左向右扫描。当遇到左括号时，左括号入栈；而遇到右括号时，首先将栈中的栈顶元素弹出栈，再比较弹出元素是否与右括号匹配，如果两者匹配，则操作继续；否则，检查出错，打印“no”，并停止操作。当表达式全部扫描完后，如果栈顶元素为“#”，说明括号作用层次嵌套正确，打印“yes”，并停止操作。 附录：STL中栈的使用 #pragma warning(disable:4786) #include stack #include iostream using namespace std ; typedef stackint STACK_INT; int main() { STACK_INT stack1; cout stack1.empty() returned (stack1.empty()? true: false) endl; // Function 3 cout stack1.push(2) endl; stack1.push(2); if (!stack1.empty()) // Function 3 cout stack1.top() returned stack1.top() endl; // Function 1 cout stack1.push(5) endl; stack1.push(5); if (!stack1.empty()) // Func