最新范文 方案 计划 总结 报告 体会 事迹 讲话 倡议书 反思 制度 入党

数据结构设计报告-栈的应用-表达式求值的设计

日期:2021-02-02  类别:最新范文  编辑:一流范文网  【下载本文Word版

数据结构设计报告-栈的应用-表达式求值的设计 本文关键词:表达式,结构设计,报告,数据,设计

数据结构设计报告-栈的应用-表达式求值的设计 本文简介:数据结构课程设计报告(2017)数据结构课程设计报告栈的应用:表达式求值的设计1目录1设计内容12设计分析12.1后缀表达式设计12.2中缀到后缀的转换设计23设计实践33.1实现要求33.2中缀表达式求值33.3后缀表达式求值43.4中缀表达式转换成后缀表达式44测试方法45程序运行效果56设计心

数据结构设计报告-栈的应用-表达式求值的设计 本文内容:

数据结构课程设计报告(2017)

数据结构课程设计报告

栈的应用:表达式求值的设计

1

1

设计内容1

2

设计分析1

2.1

后缀表达式设计1

2.2中缀到后缀的转换设计2

3设计实践3

3.1实现要求3

3.2

中缀表达式求值3

3.3后缀表达式求值4

3.4

中缀表达式转换成后缀表达式4

4测试方法4

5程序运行效果5

6

设计心得6

7

附录6

1

栈的应用:表达式的求值的设计

1

设计内容

设计一个表达式求值的程序。该程序必须可以接受包含(,),+,-,*,/,%,和^(求幂运算符,a^b=ab)的中缀表达式,并求出结果。如果表达式正确,则输出表达式的结果;如果表达式非法,则输出错误信息。

输入要求:程序从“input.txt”文件中读取信息,在这个文件中如果有多个中缀表达式,则每个表达式独占一行,程序的读取操作在文件在文件的结尾处停止。

输出要求:对于每个表达式,将其结果放在“output.txt”文件的每一行中。这些结果可能是值,也可能是错误信息“ERROR

IN

INFIX

NOTATION”。

2

设计分析

2.1

后缀表达式设计

后缀表达式是由一系列的运算符、操作数组成的表达式,其中运算符位于两个操作数之后。后缀表达式很容易通过应用栈实现表达式的计算。其基本过程是:当输入一个操作数时,它被压入栈中,当一个运算符出现时,就从栈中弹出适当数量的操作数,对该运算进行计算,计算结果再压回栈中。对于最常见的二元运算符来说,弹出的操作数只有两个。处理完整个后缀表达式之后,栈顶上的元素就是表达式的结果值。整个计算过程不需要理解计算的优先级规则。

2.2中缀到后缀的转换设计

从上面的分析可知,后缀表达式是很容易应用栈进行计算的,但要处理的是中缀表达式。同样,也可以应用栈将中缀表达式转换为后缀表达式。此时,栈里要保存的是运算符,而在后缀表达式计算中,栈里保存的是操作数。应用栈将中缀表达式转换为后缀表达式的基本过程如下。

从头到尾读取中缀表达式的每个对象,对不同对象按不同的情况处理:

●如果遇到空格,则认为是分隔符,不需处理。

●若遇到操作数,则直接输出。

●若是左括号,则将其压入至栈中。

●若遇到的是右括号,表明括号的中缀表达式已经扫描完毕,把括号中的运算符退栈,并输出。

●若遇到的是运算符,当该运算符的优先级大于栈顶运算符的优先级时,则把它压栈,当该运算符的优先级小于等于栈顶运算符时,将栈顶运算符退栈并输出,再比较新的栈顶运算符,按同样处理方法,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈。

●若中缀表达式处理完毕,则要把栈中存留的运算符一并输出。

上述处理过程的一个关键是不同运算符优先级的设置。在程序实现中,可以用一个数来代表运算符的优先级,优先级数值越大,它的优先级越高,这样的优先级的比较就转换为两个数的大小比较。

程序的整体算法过程分两步:

第一步,从“input.txt”文件中读取中缀表达式,并应用运算符栈OpHolder把中缀表达式转换为后缀表达式,将输出结果(转换后得到的后缀表达式)存放在一个temp文件中。

第二步,从temp文件中读取后缀表达式,并应用操作数栈Operands计算后缀表达式结果,将结果输出到“output.txt”文件中。

本程序中的栈采用前面所述的带头节点的链式存储结构,涉及两种类型:用于存储运算符号的char类型的链栈以及用于存储操作数的float类型的链栈。

本程序将整个求值过程分解为两个步骤:中缀表达式转换为后缀表达式、计算后缀表达式结果值。其实,可以将这两个过程统一合并在一起完成,当然也同样需要操作数和运算符这两类栈。另外,本程序中,应用函数OperatorValue来判别运算符的优先级,一种更灵活的方式是应用数组来记录各运算符的优先级。读者可应用以上思路对本程序进一步改进。

3设计实践

3.1实现要求

本程序的输入形式是“input.txt”文件,输出结果存放到“output.txt”文件中。在输入文件中等式的格式必须是中缀格式,例如1+2*3,而且每一行只允许一个表达式。

本程序将读入的中缀表达式转换为后缀表达式,并存放在temp,txt文件中;随后从temp.txt中读取后缀表达式,并将计算结果输入到output.txt中。

一个char类型的栈“Whereat”用来记录后缀表达式中操作数和运算符号的顺序,以决定需要多少次计算。

3.2

中缀表达式求值

中缀表达式:每个二目运算符在两个运算量的中间,假设操作数是整型常数,运算符只含加、减、乘、除等四种运算符,界限符有左右括号和表达式起始、结束符“#”,如:#(7+15)*(23-28/4)#。要对一个简单的算术表达式求值,首先要了解算术四则运算的规则,即:

(1)

从左到右;

(2)

先乘除,后加减;

(3)

先括号内,后括号外。

运算符和界限符可统称为算符,它们构成的集合命名为OPS。根据上述三条运算规则,在运算过程中,任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一:

θ1θ2,θ1的优先权高于θ2。

实现算符优先算法时需要使用两个工作栈:一个称作operator,用以存放运算符;另一个称作operand,用以存放操作数或运算的中间结果。算法的基本过程如下:

首先初始化操作数栈operand和运算符栈operator,并将表达式起始符“#”压入运算符栈;

依次读入表达式中的每个字符,若是操作数则直接进入操作数栈operand,若是运算符,则与运算符栈operator的栈顶运算符进行优先权比较,并做如下处理:

(1)

若栈顶运算符的优先级低于刚读入的运算符,则让刚读入的运算符进operator栈;

(2)

若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入θ,同时将操作数栈operand退栈两次,得到两个操作数a、b,对a、b进行θ运算后,将运算结果作为中间结果推入operand栈;

(3)

若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符(左括号)退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时,说明表达式起始符“#”与表达式结束符“#”相遇,整个表达式求解结束。

3.3后缀表达式求值

计算一个后缀表达式,算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法:只使用一个对象栈,当从左向右扫描表达式时,每遇到一个操作数就送入栈中保存,每遇到一个运算符就从栈中取出两个操作数进行当前的计算,然后把结果再入栈,直到整个表达式结束,这时送入栈顶的值就是结果。

下面是后缀表达式求值的算法,在下面的算法中假设,每个表达式是合乎语法的,并且假设后缀表达式已被存入一个足够大的字符数组A中,且以‘#’为结束字符,为了简化问题,限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题。

3.4

中缀表达式转换成后缀表达式

将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似,但只需要运算符栈,遇到运算对象时直接放后缀表达式的存储区,假设中缀表达式本身合法且在字符数组A中,转换后的后缀表达式存储在字符数组B中。具体做法:遇到运算对象顺序向存储后缀表达式的B数组中存放,遇到运算符时类似于中缀表达式求值时对运算符的处理过程,但运算符出栈后不是进行相应的运算,而是将其送入B中存放,程序的整体算法分两步:

第一步,从”input.txt”文件中读取中缀表达式,并应用运算符栈OpHolder把中缀表达式转换为后缀表达式,将输出结果存放在一个temp文件中。

第二步,从temp文件中读取中缀表达式,并应用操作栈Operands计算后缀表达式结果,将结果输出到”output.txt”文件中。

4测试方法

测试项目

测试实例

期望测试结果

基本测试

3.00

3.00

1+2+3-4

2.00

1

+

2

3.00

4.99+5.99+6.99*1.06

18.39

(3*5*(4+8)%2)

0.00

2^2^3

256.00

2^2.5^3

50535.16

(2-4)^3

-8.00

扩展测试

2.5-3.4/2+1*2

2.80

(2.5)*(3-2)+5.6-190%3^2^(1+1)

-19.90

1+2+3

6.00

1*2*3

6.00

(1+2)*3+4/(5+1*4)+3.26

12.70

3+4-6.7+8

8.30

2.9*1.2+0.5-4%3/2+4^(5-5)

4.48

2^3-(5+2)/7*9

-1.00

50-3^2^2+4%2-7*(3)

-52.00

(((2))-3)

-1.00

2.5^2

6.25

2^(4.4-2.4)

4.00

2^(4.4-3.1)

2.46

(2-4)^3

-8.00

(2-4)^(5-8)

-0.13

容错测试

1+2(

ERROR

IN

INFIX

NOTATION

2/0

ERROR

IN

INFIX

NOTATION

2%0

ERROR

IN

INFIX

NOTATION

(2-4)^3.1

ERROR

IN

INFIX

NOTATION

2.5%2

ERROR

IN

INFIX

NOTATION

2%2.5

ERROR

IN

INFIX

NOTATION

2+3)(-5

ERROR

IN

INFIX

NOTATION

(((2))-3))

ERROR

IN

INFIX

NOTATION

((((2))-3)

ERROR

IN

INFIX

NOTATION

3.5/(1-1)

ERROR

IN

INFIX

NOTATION

(5.6-2)%3

ERROR

IN

INFIX

NOTATION

5%(3.2-2.1)

ERROR

IN

INFIX

NOTATION

3.0.2+1

ERROR

IN

INFIX

NOTATION

1+++1

ERROR

IN

INFIX

NOTATION

1#1

ERROR

IN

INFIX

NOTATION

2

2

ERROR

IN

INFIX

NOTATION

+-+

ERROR

IN

INFIX

NOTATION

5程序运行效果

输入如下:

输出如下:

6

设计心得

通过这次课程设计,增加了我对数据结构知识的了解。在具体操作中,也发现自己的不足之处,对于所学知识的理解还不够深刻,运用起来也不够熟练。发现上机调试的重要作用,特别是对对栈处理的基本算法如判空、压栈、弹栈、栈元素倒置等知识的运用有了有了更深的理解。通过实际操作,学会

利用数据结构进行编程的基本思想与方法同时也了解了实验报告撰写的基本要求。

回顾起此次课程设计,从拿到题目到完成整个编程,从理论到实践,在这些日子里,可以学到很多很多的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。同时,我们不能只局限于将书本上的代码看懂,会调试运行,我们要善于发现问题,提出自己的想法,联系实际生活,开拓思维,对程序进行改进和完善。我们要学会通过网络、书籍等多途径。通过这次课程设计使我们懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论。

7

附录

#include

#include

#include

int

PrintError

=

0;

/*全局变量,0代表正常,1代表表达式出错*/

/*char类型链表式堆栈,用来存放运算符号,以及用在中缀表达式转换等时候*/

typedef

struct

NodePtrToNode;

typedef

PtrToNode

Stack;

int

IsEmpty(Stack

S);

void

MakeEmpty(Stack

S);

void

Push(char

X,Stack

S);

char

Top(Stack

S);

void

Pop(Stack

S);

typedef

struct

Node{

char

Element;

PtrToNode

Next;

};

/*float类型链表式堆栈,用来存放操作数*/

typedef

struct

FNodePtr_Fn;

typedef

Ptr_Fn

FStack;

int

FisEmpty(FStack

S);

void

FPush(float

X,FStack

S);

float

FTop(FStack

S);

void

FPop(FStack

S);

typedef

struct

FNode{

float

Element;

Ptr_Fn

Next;

};

void

ConvertToPost(FILEIn,Stack

Whereat,FILETemp);

void

Reverse(Stack

Rev);

void

Calculate(FILEChange,Stack

Whereat,FILETemp);

/******主函数******/

int

main()

{

FILEInputFile,*OutputFile,*Temp;/*初始化变量*/

Stack

Whereat;

char

sample;

InputFile

=

fopen(“Input.txt“,“r“);/*打开文件*/

OutputFile

=

fopen(“Output.txt“,“w“);

Whereat

=

malloc(sizeof(struct

Node));/*给

Whereat分配空间*/

Whereat->Next

=

NULL;

if

(!InputFile

||

!OutputFile)

{

/*错误处理*/

printf(“intput

or

output

file(s)

do

not

exist./n“);

return(1);

}

sample

=

getc(InputFile);

while

(

sample

!=

EOF){

Temp

=

fopen(“Temp.txt“,“w+“);

/*生成Temp文件*/

ungetc(sample,InputFile);

/*

put

back

sample字符*/

ConvertToPost(InputFile,Whereat,Temp);

/*中缀变后缀*/

if

(PrintError){

/*错误处理*/

fprintf(OutputFile,“Error

in

infix

notation.“);

fscanf(InputFile,“/n“,PrintError

=

0;

}

else

if

(IsEmpty(Whereat)

==

1){

/*跳过在input文件中的空格*/

}

else

if

(IsEmpty(Whereat)

!=

1){

Reverse(Whereat);

if

(Top(Whereat)

==

B

){

/*错误处理,*/

/*A表示操作数B表示运算符*/

PrintError

=

1;

/*后缀表达式第一个元素应是操作数而不是运算符号*/

}

fclose(Temp);

Temp

=

fopen(“Temp.txt“,“r+“);

Calculate(OutputFile,Whereat,Temp);/*计算结果*/

}

fclose(Temp);

MakeEmpty(Whereat);/*

清空Whereat用来处理下一行*/

putc(

/n,OutputFile);/*

在输出文件中换行*/

sample

=

getc(InputFile);

}

/*

While循环结束*/

free(Whereat);

fclose(InputFile);

fclose(OutputFile);

remove(“Temp.txt“);

/*

删除Temp.txt*/

return

1;

}

/******检查堆栈是否为空******/

int

IsEmpty(Stack

S)

{

return(S->Next==NULL);

}

/******检查float堆栈是否为空******/

int

FIsEmpty(FStack

S)

{

return(S->Next==NULL);

}

/******弹出栈顶元素******/

void

Pop(Stack

S)

{

PtrToNode

FirstCell;

if

(IsEmpty(S))

perror(“Empty

Stack“);

else{

FirstCell

=

S->Next;

S->Next

=

S->Next->Next;

free(FirstCell);

}

}

/******弹出float栈顶元素******/

void

FPop(FStack

S)

{

Ptr_Fn

FirstCell;

if

(FIsEmpty(S))

perror(“Empty

Stack“);

else{

FirstCell

=

S->Next;

S->Next

=

S->Next->Next;

free(FirstCell);

}

}

/******将堆栈置空******/

void

MakeEmpty(Stack

S)

{

if

(S

==

NULL)

perror(“Must

use

Createstack

first“);

else

while

(!IsEmpty(S))

Pop(S);

}

/******将float堆栈置空******/

void

FMakeEmpty(FStack

S)

{

if

(S

==

NULL)

perror(“Must

use

Createstack

first“);

else

while

(!IsEmpty(S))

Pop(S);

}

/******元素进栈******/

void

Push(char

X,Stack

S)

{

PtrToNode

TmpCell;

TmpCell

=

(PtrToNode)malloc(sizeof(struct

Node));

if

(TmpCell

==

NULL)

perror(“Out

of

Space!“);

else{

TmpCell->Element

=

X;

TmpCell->Next

=

S->Next;

S->Next

=

TmpCell;

}

}

/******float元素进栈******/

void

FPush(float

X,FStack

S)

{

Ptr_Fn

TmpCell;

TmpCell

=

(Ptr_Fn)malloc(sizeof(struct

FNode));

if

(TmpCell

==

NULL)

perror(“Out

of

Space!“);

else{

TmpCell->Element

=

X;

TmpCell->Next

=

S->Next;

S->Next

=

TmpCell;

}

}

/******返回栈顶元素******/

char

Top(Stack

S)

{

if

(!IsEmpty(S))

return

S->Next->Element;

perror(“Empty

Stack“);

exit(1);

return

0;

}

/******返回float栈顶元素******/

float

FTop(FStack

S)

{

if

(!FIsEmpty(S))

return

S->Next->Element;

perror(“Empty

Stack“);

exit(1);

return

0;

}

/******将堆栈元素倒置******/

void

Reverse(Stack

Rev)

{

Stack

Tempstack;

Tempstack

=

malloc(sizeof(struct

Node));

Tempstack->Next

=

NULL;

while

(!IsEmpty(Rev)){

Push(Top(Rev),Tempstack);

/*将元素压栈到一个临时堆栈*/

Pop(Rev);

}

Rev->Next

=

Tempstack->Next;

/*指向新的堆栈*/

}

/*******

Whereat

说明:

Whereat

记录了操作数和运算符号的位置,用A和B区分。A

=

operand,B

=

operator.

(例如

1+2转换成12+,在whereat中的形式应该是

AAB)

OpHolder说明:

Char类型的堆栈Opholder用来保存运算符号。*****/

/******将中缀表带式转换为后缀表达式******/

void

ConvertToPost(FILEIn,Stack

Whereat,FILETemp)

{

Stack

OpHolder;

char

holder;

char

lastseen;

int

digitcounter

=

0;

/*操作数的计数器*/

OpHolder

=

malloc(sizeof(struct

Node));

/*初始化*/

OpHolder->Next

=

NULL;

holder=getc(In);

lastseen

=

@

;

/*用来防止输入格式错误,例如两个小数点*/

putc(,Temp);

while

((holder

!=

/n

)

}

else

if

(

IsOperator(holder)

==

-1){

/*如果holder不是操作数或运算符号*/

PrintError

=

1;

}

else

if

(IsOperator(holder)==0){

if

((lastseen

==

holder)

}

else

lastseen

=

holder;

if

(digitcounter

==

0){

Push(

A,Whereat);

/*进栈*/

digitcounter++;/*计数器加一*/

putc(,Temp);

}

putc(holder,Temp);

}

else{

digitcounter

=

0;

if

((lastseen

==

holder)

else

lastseen

=

holder;

if(IsEmpty(OpHolder)==1){

/*当OpHolder为空*/

Push(holder,OpHolder);

}

else

if(OperatorValue(Top(OpHolder))

==

6){

/*OpHolder是“(“的情况*/

if(OperatorValue(holder)==5)

Pop(OpHolder);

else

Push(holder,OpHolder);

}

else

if(OperatorValue(holder)

==

6){

Push(holder,OpHolder);

}

else

if(OperatorValue(holder)

==

5){

/*

OpHolder是“)“的情况*/

while

((IsEmpty(OpHolder)

!=

1)

Push(

B,Whereat);

putc(Top(OpHolder),Temp);

Pop(OpHolder);

}

if

(IsEmpty(OpHolder)

==

1){

/*错误处理,括号不匹配*/

PrintError

=

1;

}

else

Pop(OpHolder);

}

else

if((OperatorValue(holder)

==

OperatorValue(Top(OpHolder)))

}

else

if((OperatorValue(holder)

=

OperatorValue(holder)){

while((IsEmpty(OpHolder)

!=

1)

putc(Top(OpHolder),Temp);

Push(

B,Whereat);

Pop(OpHolder);

}

Push(holder,OpHolder);

}

else

if(OperatorValue(Top(OpHolder))

Next=

NULL;

while

((IsEmpty(Whereat)

!=

1)

fscanf(Temp,“%f“,/*如果是A,则是操作数*/

FPush(looker,Operands);

Pop(Whereat);

}

else

if

(Top(Whereat)

==

B

){

fscanf(Temp,““,/*如果是B,则是运算符*/

Op

=

getc(Temp);

switch(Op){

/*

判断是什么运算符*/

case(

^

):

/*幂运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){

/*错误处理*/

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

if

((NumA

==

0

}

else{

answer

=

pow(NumA,NumB);

FPush(answer,Operands);

}

}

break;

case

%

:

/*取模运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){/*错误处理*/

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

if

((NumA

-

(int)NumA

!=

0)

||

(NumB

-

(int)NumB

!=

0)

||

(NumB

==

0))

{

PrintError

=

1;

}

else{

answer

=

(int)NumA

%

(int)NumB;

/*

x

mod

b*/

FPush(answer,Operands);

}

}

break;

case

:

/*乘法运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

answer

=

NumA

NumB;

/*

x

y*/

FPush(answer,Operands);

}

break;

case

/

:

/*除法运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

if

(NumB

==

0){

PrintError

=

1;

/*分母不为0*/

}

else{

answer

=

(float)(NumA

/

NumB);

/*

x

/

y*/

FPush(answer,Operands);

}

}

break;

case

+

:

/*加法运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

answer

=

NumA

+

NumB;/*

x

+

y*/

FPush(answer,Operands);

}

break;

case

-

:

/*减法运算*/

NumB

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)){

PrintError

=

1;

}

else{

NumA

=

FTop(Operands);

FPop(Operands);

answer

=

NumA

-

NumB;/*

x

-

y*/

FPush(answer,Operands);

}

break;

default:

PrintError

=

1;

break;

}

/*判断结束*/

Pop(Whereat);

}

}

/*循环结束*/

if

(!PrintError){

answer

=

FTop(Operands);

FPop(Operands);

if

(FIsEmpty(Operands)

!=

1){

fprintf(Change,“Error

in

infix

notation.“);

/*如果还有操作数*/

PrintError

=

0;

}

else

fprintf(Change,“%.2f“,answer);

}

else{

fprintf(Change,“Error

in

infix

notation.“);

PrintError

=

0;

}

FMakeEmpty(Operands);

free(Operands);

}

15

篇2:数据结构实习报告:设计一个演示用运算优先法对算数表达式求值过程的程序

数据结构实习报告:设计一个演示用运算优先法对算数表达式求值过程的程序 本文关键词:数据结构,算数,表达式,运算,演示

数据结构实习报告:设计一个演示用运算优先法对算数表达式求值过程的程序 本文简介:实习报告题目:设计一个演示用运算优先法对算数表达式求值过程的程序。班级:姓名:学号:完成日期:一、需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式,本程序需要用户自行输入表达式(运算符可以是加(+);减(-);乘(*);除(/)

数据结构实习报告:设计一个演示用运算优先法对算数表达式求值过程的程序 本文内容:

实习报告

题目:设计一个演示用运算优先法对算数表达式求值过程的程序。

班级:

姓名:

学号:

完成日期:

一、

需求分析

1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.

2用户输入以“#”结尾的算数表达式,本程序需要用户自行输入表达式(运算符可以是加(+);减(-);乘(*);除(/);括号(())),以字符形式读入,在读入的同时,完成运算符和运算数的识别处理,在识别出运算数的同时,要将其字符序列形式转换成整数形式。

3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容,即演示运算操作。

4测试数据见原题。

5程序执行的命令包括:

(1)

建立算数表达式;

(2)

得到运算表达式的值;

(3)

演示运算过程。

二、

概要设计

1.

设定栈的抽象数据类型定义:

ADT

Stack{

数据对象

D={

ai

|

ai

∈charSet,i=1,2,.,n,n≥0

}

数据关系:

R1={

|

ai-1,ai∈D,i=2,.,n

}

(约定an

端为栈顶,a1

端为栈底)

基本操作:

InitStack(

inttop;

int

stacksize;

}SqStack1;//操作数栈

typedef

struct{

charbase;

chartop;

int

stacksize;

}SqStack2;//操作符栈

2、

栈类型

typedef

struct{

charbase;

chartop;

int

stacksize;

}Stack;

//栈类型

栈的基本操作设置如下:

void

InitStack(Stack

S.top=p;

S.size++;

Return

TRUE;

}

else

return

FALSE;

}

Status

Pop(Stack

else{

p=S.top;S.top=S.top->next;

e=p->:data;S.size--;

return

TRUE;

}

}

3、运算代码

int

Operate(int

a,char

theta,int

b)

//计算表达式值:主要是将大的表达式转化成小的表达式进行逐步求值

{

int

c;

if(theta==

+

)

c=a+b;

else

if(theta==

-

)

c=a-b;

else

if(theta==

)

c=a*b;

else

c=a/b;

return

c;

}//Operate

int

result(SqStack1OPND,SqStack2OPTR)

//求值

{

char

a=0;

char

theta;

int

b,c,number=0;

IntInitStack(OPND);

CharInitStack(OPTR);

CharPush(OPTR,#

);

a=getchar();

while(a!=

#

||

CharGetTop(OPTR)!=

#

)

{

printf(“输入字符:%c

“,a);

if(!In(a))//不是运算符则进栈

{

number=0;

while(!In(a))

{

number

=

number*10

+(a-48);//处理多位整数z=10*x+y

a

=

getchar();

}

IntPush(OPND,number);

printf(“主要操作:Push(OPND,%d)

“,number);

}

else

switch(Precede(a,CharGetTop(OPTR)))

{

case

:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作:Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈:%d

OPTR栈:%c/n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“The

result

is

%d./n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

4.主函数和其他函数的代码

void

main()

//主函数,使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“Please

enter

an

expression

with

a

end

of

#

./n“);

printf(“The

Expression:“);

result(OPND,OPTR);

}

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,#include

#include

#include

#define

STACK_INIT_SIZE

100

#define

STACKINCREMENT

10

#define

ERROR

0

#define

OK

1

//********************************************栈模块

typedef

struct

SqStack1//运算数栈

{

intbase;

inttop;

int

stacksize;

}SqStack1;

typedef

struct

SqStack2//运算符栈

{

charbase;

chartop;

int

stacksize;

}SqStack2;

void

IntInitStack(SqStack1S)

{

S->base=(int)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

void

CharInitStack(SqStack2S)

{

S->base=(char)malloc(STACK_INIT_SIZE*sizeof(char));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

int

IntGetTop(SqStack1S)

//取栈顶元素

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

char

CharGetTop(SqStack2S)

//取栈顶元素

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

int

IntPush(SqStack1S,int

e)

{(*S).top++=e;

return

OK;

}

int

CharPush(SqStack2S,char

e)

{(*S).top++=e;

return

OK;

}

int

IntPop(SqStack1S)

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

int

CharPop(SqStack2S)

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

//——————————————————*******************运算模块

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作:Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈:%d

OPTR栈:%c/n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“/n结果:%d./n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

//————————————————————————主程序模块

void

main()

//主函数,使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“请输入算数表达式并以

#

结尾./n“);

printf(“算数表达式:“);

result(OPND,OPTR);

}

篇3:ID正则表达式用法及介绍

ID正则表达式用法及介绍 本文关键词:用法,介绍,正则表达式,ID

ID正则表达式用法及介绍 本文简介:ID正则表达式用法及介绍[复制链接]本帖最后由漫步云中于2011-2-1811:23编辑ID正则表达式用处很广,正则表达比较复杂的东西,只有不断用到,摸索,就能得心应手!例1:如果要把蓝色数据要替换成这右边的[?],有什么比较快捷的方法吗,也就是把左边蓝色底文字的数字全都替换成右边的[?],就用到正

ID正则表达式用法及介绍 本文内容:

ID正则表达式用法及介绍

[复制链接]

本帖最后由

漫步云中

2011-2-18

11:23

编辑

ID正则表达式用处很广,正则表达比较复杂的东西,只有不断用到,摸索,就能得心应手!

例1:

如果要把蓝色数据要替换成这右边的[?],有什么比较快捷的方法吗,

也就是把左边蓝色底文字的数字全都替换成右边的[?],就用到正则表达式:

用查找替换。

选中整列后

用Grep

查找

.+

替换为

[?],见下图

例2

如果把下面对话的人名统一修改格式,英文的加蓝加粗。中文的加蓝变粗宋。因为整本书有几百个不一样的人名,如果用替换的话也是一个大工程,用GREP可以做到:(也可以用嵌套样式)

GREP

代码查找参考如下:

代码:^.+?(:|:)

替换如图:

1.

grep简介

egrep和fgrep的命令只跟grep有很小不同。egrep是grep的扩展,支持更多的re元字符,

fgrep就是fixed

grep或fast

grep,它们把所有的字母都看作单词,也就是说,正则表达式中的元字符表示回其自身的字面意义,不再特殊。linux使用GNU版本的grep。它功能更强,可以通过-G、-E、-F命令行选项来使用egrep和fgrep的功能。

grep的工作方式是这样的,它在一个或多个文件中搜索字符串模板。如果模板包括空格,则必须被引用,模板后的所有字符串被看作文件名。搜索的结果被送到屏幕,不影响原文件内容。

grep可用于shell脚本,因为grep通过返回一个状态值来说明搜索的状态,如果模板搜索成功,则返回0,如果搜索不成功,则返回1,如果搜索的文件不存在,则返回2。我们利用这些返回值就可进行一些自动化的文本处理工作。

2.

grep正则表达式元字符集(基本集)

^

锚定行的开始

如:

^grep

匹配所有以grep开头的行。

$

锚定行的结束

如:

grep$

匹配所有以grep结尾的行。

.

匹配一个非换行符的字符

如:

gr.p

匹配gr后接一个任意字符,然后是p。

匹配零个或多个先前字符

如:grep

匹配所有一个或多个空格后紧跟grep的行。

.*一起用代表任意字符。

[]

匹配一个指定范围内的字符,如

[Gg]rep

匹配Grep和grep。

[^]

匹配一个不在指定范围内的字符,如:

[^A-FH-Z]rep

匹配不包含A-F和H-Z的一个字母开头,紧跟rep的行。

/(/)

标记匹配字符,如

/(love/)

,love被标记为1。

/

匹配包含以grep结尾的单词的行。

x/{m/}

重复字符x,m次,如:

o/{5/}

匹配包含5个o的行。

x/{m,/}

重复字符x,至少m次,如:

o/{5,/}

匹配至少有5个o的行。

x/{m,n/}

重复字符x,至少m次,不多于n次,如:

o/{5,10/}

匹配5--10个o的行。

/w

匹配文字和数字字符,也就是[A-Za-z0-9],如:

G/w*p

匹配以G后跟零个或多个文字或数字字符,然后是p。

/W

/w的反置形式,匹配一个或多个非单词字符,如点号句号等。

/b

单词锁定符,如:

/bgrep/b

只匹配grep。

3.

用于egrep和

grep

-E的元字符扩展集

+

匹配一个或多个先前的字符。如:

[a-z]+able

,匹配一个或多个小写字母后跟able的串,如loveable,enable,disable等。

?

匹配零个或多个先前的字符。如:

gr?p

匹配gr后跟一个或没有字符,然后是p的行。

a|b|c

匹配a或b或c。如:grep|sed匹配grep或sed

()

分组符号,如:love(able|rs)ov+匹配loveable或lovers,匹配一个或多个ov。

x,x{m,},x{m,n}

作用同x/{m/},x/{m,/},x/{m,n/}

4.

POSIX字符类

为了在不同国家的字符编码中保持一至,POSIX(The

Portable

Operating

System

Interface)增加了特殊的字符类,如[:alnum:]是A-Za-z0-9的另一个写法。要把它们放到[]号内才能成为正则表达式,如[A-

Za-z0-9]或[[:alnum:]]。在linux下的grep除fgrep外,都支持POSIX的字符类。

[:alnum:]

文字数字字符

[:alpha:]

文字字符

[:digit:]

数字字符

[:graph:]

非空字符(非空格、控制字符)

[:lower:]

小写字符

[:cntrl:]

控制字符

[:print:]

非空字符(包括空格)

[:punct:]

标点符号

[:space:]

所有空白字符(新行,空格,制表符)

[:upper:]

大写字符

[:xdigit:]

十六进制数字(0-9,a-f,A-F)

5.

Grep命令选项

-?

同时显示匹配行上下的?行,如:grep

-2

pattern

filename同时显示匹配行的上下2行。

-b,--byte-offset

打印匹配行前面打印该行所在的块号码。

-c,--count

只打印匹配的行数,不显示匹配的内容。

-f

File,--file=File

从文件中提取模板。空文件中包含0个模板,所以什么都不匹配。

-h,--no-filename

当搜索多个文件时,不显示匹配文件名前缀。

-i,--ignore-case

忽略大小写差别。

-q,--quiet

取消显示,只返回退出状态。0则表示找到了匹配的行。

-l,--files-with-matches

打印匹配模板的文件清单。

-L,--files-without-match

打印不匹配模板的文件清单。

-n,--line-number

在匹配的行前面打印行号。

-s,--silent

不显示关于不存在或者无法读取文件的错误信息。

-v,--revert-match

反检索,只显示不匹配的行。

-w,--word-regexp

如果被/引用,就把表达式做为一个单词搜索。

-V,--version

显示软件版本信息。

6.

实例

要用好grep这个工具,其实就是要写好正则表达式,所以这里不对grep的所有功能进行实例讲解,只列几个例子,讲解一个正则表达式的写法。

$

ls

-l

|

grep

^a

通过管道过滤ls

-l输出的内容,只显示以a开头的行。

$

grep

test

d*

显示所有以d开头的文件中包含test的行。

$

grep

test

aa

bb

cc

显示在aa,bb,cc文件中匹配test的行。

$

grep

[a-z]/{5/}

aa

显示所有包含每个字符串至少有5个连续小写字符的字符串的行。

$

grep

w/(es/)t.*/1

aa

如果west被匹配,则es就被存储到内存中,并标记为1,然后搜索任意个字符(.*),这些字符后面紧跟着另外一个es(/1),找到就显示该行。如果用egrep或grep

-E,就不用“/“号进行转义,直接写成

w(es)t.*/1

就可以了。

7.注意

在某些机器上,要使用-E参数才能够进行逻辑匹配(详见下)

grep

“a|b“(匹配包含字符样式为“a|b“的行)

grep

-E

“a|b“(匹配包含字符样式为“a“或“b“的行)

man

grep里面关于-E参数的说明是

-E

Treats

each

pattern

specified

as

an

extended

regular

expression

(ERE).

A

NULL

value

for

the

ERE

matches

every

line.

Note:

The

grep

command

with

the

-E

flag

is

the

same

as

the

egrep

command,except

that

error

and

usage

messages

are

different

and

the

-s

flag

functions

differently

    以上《数据结构设计报告-栈的应用-表达式求值的设计》范文由一流范文网精心整理,如果您觉得有用,请收藏及关注我们,或向其它人分享我们。转载请注明出处 »一流范文网»最新范文»数据结构设计报告-栈的应用-表达式求值的设计
‖大家正在看...
设为首页 - 加入收藏 - 关于范文吧 - 返回顶部 - 手机版
Copyright © 一流范文网 如对《数据结构设计报告-栈的应用-表达式求值的设计》有疑问请及时反馈。All Rights Reserved