数据结构课程设计

数据结构课程设计
预览:

Project1简单编译器表达式处理的模拟

(一)语法检查

1)括号匹配的检验

【问题描述】

假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或[([ ][ ])]等为正确表达式,[ ( ] )或( ( ( ]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:

[ ( [ ] [ ] ) ]

1 2 3 4 5 6 7 8

当计算机接受了第一个括号以后,他期待着与其匹配的第8个括号的出现,然而等来的却是第二个括号,此时第一个括号”[“只能暂时靠边,而迫切等待与第二个括号相匹配的第7个括号的出现,类似的,因只等来了第三个括号“[“,此时,其期待的紧迫程度较第二个括号更紧迫,则第二个括号只能靠边,让位于第三个括号,显然第三个括号的期待紧迫程度高于第2个,而第二个括号的期待紧迫程度高于第一个括号;在接受了第4个括号之后,第三个括号的群殴带得到了满足,消解之后,第二个括号的期待匹配就成了最紧迫的任务了,…….,依次类推。可见这个处理过程正好和栈的特点相吻合。

【基本要求】

读入圆括号和方括号的任意序列,输出“匹配”或“此串括号匹配不合法”。

【测试数据】

输入([ ] ()),结果“匹配”

输入[ ( ) ],结果“此串括号匹配不合法”

【测试提示】

设置一个栈,每读入一个括号,若是左括号,则作为一个新的更紧迫的期待压入栈中;

若是右括号,并且与当前栈顶的左括号相匹配,则将当前栈顶的左括号退出,继续读下一个括号,如果读入的右括号与当前栈顶的左括号不匹配,则属于不合法的情况;

在初始和结束时,栈应该是空的。

【选作内容】

考虑增加大括号的情况

2)表达式合法性检查

【问题描述】

假设表达式中允许初显的运算符有+ 、-、*、/、%共五种,不允许省略运算符,

且都是双目运算符,要求设计算法检查输入的表达式是否符合书写规范。

【基本要求】如果通过合法检查,则进入下一个环节——求值;如果不合法,则应像编译器一样,根据不同的错误种类给出相应的提示。

(二)表达式求值

【问题描述】如果输入的表达式通过语法检查,设计算法模拟完成对表达式求值的过程。

【实现提示】利用栈完成后表达式求值过程,可以有不同的方法。如:使用符号表;使用后缀表达式;使用二叉树等。

Project2.停车场管理

第1页/共8页 下一页>尾页

寻找更多 "数据结构课程设计"