数据结构设计报告-栈应用-表达式求值设计
数据结构设计报告-栈的应用-表达式求值的设计 本文关键词：表达式，结构设计，报告，数据，设计
数据结构设计报告-栈的应用-表达式求值的设计 本文简介：数据结构课程设计报告（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