project+3.doc Project 3: Implementation and Applications of Stacks 工程 3: 堆栈的实现和应用 Problems 1. Write a Conversion function to converse any decimal data to binary version. 写一个 Conversion 函数来实现将十进制数转换成二进制数。 Demands: 实验要求: (1) Implement Stack ADT using linked list representation, which must at least has five basic operations: Create , IsFull , Push , IsEmpty and Pop . (1) 使用链表实现堆栈的五个基本函数: Create , IsFull , Push , IsEmpty and Pop . (2) Implement the Conversion function using the previous five stack operations. (2) 用堆栈的这 5 个函数来实现 Conversion , (3) Complete the whole project, in which the input and output should be according to the following format: (3) 完成整个工程,其输入和输出必须按照以下格式: Please input the decimal number: 10 The corresponding binary version is: 1010 Please input the decimal number: 11 The corresponding binary version is: 1011 Please input the decimal number: -1 Bye! 注:完成该程序的同学请登陆数据结构 ACM 在线测试网站: http://ds.imedialab.info/ ,用自己的和姓名注册,然后完成 http://ds.imedialab.info/problem.php?id=1004 。 2. Write a program to judge whether a bracket sequence (maybe has other letters) is “matching”. The “matching” means that if there has a ‘(‘ in a expression and there must has a ‘)’ in it .If the input sequence is “matching”, then output ‘ok’, otherwise output ‘ERROR’. 2. 写一个判断表达式括号是否“匹配”。“匹配”是指如果有一个 ’(’ 则必须在后面有一个 ’)’ 。如果匹配,则输出 ’ok’ ,否则输出 ’ERROR’ 。 Demands (1) Implement Stack using array representation. 用数组实现堆栈。 (2) Build a new project to implement the bracket Matching function. 实现 Matching 函数。 (3) The input and output should be according to the following format: 完成整个程序,输入输出必须按照以下格式: Please input the expression: a*(b+c) The bracket of the expression is matching OK ! Please input the expression: a*(b+c)) The bracket of the expression is matching ERROR ! Please input the expression: (a*(b+c) The bracket of the expression is matching ERROR ! Note 注意 The two implementation of Stack should be written in separated files (.cpp and .h) in the VC++ workspace. Their files should be named differently. 堆栈的两种实现必须分别在不同的源文件和头文件中完成,他们的文件名应有区分。