《数据结构》算术表达式求值.doc

《数据结构》算术表达式求值优质资料
(可以直接使用，可编辑 优质资料，欢迎下载）
二 课程设计2——算术表达式求值
一、 需求分析
二、 程序的主要功能
三、 程序运行平台
四、 数据结构
五、 算法及时间复杂度
六、 测试用例
七、 程序源代码
三 感想体会与总结

算术表达式求值
一、需求分析
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
二、程序的主要功能
（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
三、程序运行平台
Visual C++ 6.0版本
四、数据结构
本程序的数据结构为栈。
（1）运算符栈部分：
struct SqStack //定义栈
{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //栈的长度
};

int InitStack (SqStack &s) //建立一个空栈S
{
if (!(s.base = (char *)malloc(50 * sizeof(char))))
exit(0);
s.top=s.base;
s.stacksize=50;
return OK;
}

char GetTop(SqStack s,char &e) //运算符取栈顶元素
{

if (s.top==s.base) //栈为空的时候返回ERROR
{
printf("运算符栈为空!\n");
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK
return OK;
}

int Push(SqStack &s,char e) //运算符入栈
{

if (s.top-s.base >= s.stacksize)
{
printf("运算符栈满!\n");

s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //栈满的时候，追加5个存储空间
if(!s.base) exit (OVERFLOW);

s.top=s.base+s.stacksize;
s.stacksize+=5;
}
*(s.top)++=e; //把e入栈
return OK;
}

int Pop(SqStack &s,char &e) //运算符出栈
{
if (s.top==s.base) //栈为空栈的时候，返回ERROR
{
printf("运算符栈为空!\n");
return ERROR;
}
else
{
e=*--s.top; //栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OK
return OK;
}
}

int StackTraverse(SqStack &s) //运算符栈的遍历
{
char *t;
t=s.base ;
if (s.top==s.base)
{
printf("运算符栈为空!\n"); //栈为空栈的时候返回ERROR
return ERROR;
}
while(t!=s.top)
{
printf(" %c",*t); //栈不为空的时候依次取出栈内元素
t++;
}
return ERROR;
}

（2） 数字栈部分：
struct SqStackn //定义数栈
{
int *base; //栈底指针
int *top; //栈顶指针
int stacksize; //栈的长度
};

int InitStackn (SqStackn &s) //建立一个空栈S
{
s.base=(int*)malloc(50*sizeof(int));
if(!s.base)exit(OVERFLOW); //存储分配失败
s.top=s.base;
s.stacksize=50;
return OK;
}

int GetTopn(SqStackn s,int &e) //数栈取栈顶元素

{
if (s.top==s.base)
{
printf("运算数栈为空!\n"); //栈为空的时候返回ERROR
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OK
return OK;
}

int Pushn(SqStackn &s,int e) //数栈入栈
{
if (s.top-s.base >=s.stacksize)
{
printf("运算数栈满!\n"); //栈满的时候，追加5个存储空间

s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) );
if(!s.base) exit (OVERFLOW);

s.top=s.base+s.stacksize; //插入元素e为新的栈顶元素
s.stacksize+=5;
}
*(s.top)++=e; //栈顶指针变化
return OK;
}

int Popn(SqStackn &s,int &e) //数栈出栈
{
if (s.top==s.base)
{
printf(" 运算符栈为空!\n"); //栈为空栈的视时候，返回ERROR

return ERROR;
}
else
{
e=*--s.top; //栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OK
return OK;
}
}

int StackTraversen(SqStackn &s) //数栈遍历

{
int *t;
t=s.base ;
if (s.top==s.base)
{
printf(" 运算数栈为空!\n"); //栈为空栈的时候返回ERROR
return ERROR;
}
while(t!=s.top)
{
printf(" %d",*t); //栈不为空的时候依次输出
t++;
}
return ERROR;
}

五、算法及时间复杂度
1、算法：
建立两个不同类型的空栈，先把一个‘# ’压入运算符栈。输入一个算术表达式的字符串（以‘#’结束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个‘#’遇到一起则运算结束。数字栈顶的数字就是要求的结果。
2、时间复杂度：O(n)
数据压缩存储栈，其操作主要有：
建立栈int Push(SeqStack *S, char x)
入栈int Pop(SeqStack *S, char x)
出栈。
以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在输入操作。
六、 测试用例
如图所示。

最终结果如图所示：

七、 源代码
/**************************************************************************************************
第七题 算术表达式求值
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，
运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，
如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。
编程利用“算符优先法”求算术表达式的值。
[基本要求]
（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
***************************************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <ctype.h>

#define OK 1
#define ERROR 0

#define STACK_INIT_SIZE 100
//#define STACKINCREMENT 10

//========================================================
// 以下定义两种栈，分别存放运算符和数字
//========================================================

//*******************运算符栈部分*************************

struct SqStack //定义栈
{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //栈的长度
};

int InitStack (SqStack &s) //建立一个空栈S
{
if (!(s.base = (char *)malloc(50 * sizeof(char))))
exit(0);
s.top=s.base;
s.stacksize=50;
return OK;
}

char GetTop(SqStack s,char &e) //运算符取栈顶元素
{

if (s.top==s.base) //栈为空的时候返回ERROR
{
printf("运算符栈为空!\n");
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK
return OK;
}

int Push(SqStack &s,char e) //运算符入栈
{

if (s.top-s.base >= s.stacksize)
{
printf("运算符栈满!\n");

s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //栈满的时候，追加5个存储空间
if(!s.base) exit (OVERFLOW);

s.top=s.base+s.stacksize;
s.stacksize+=5;
}
*(s.top)++=e; //把e入栈
return OK;
}

int Pop(SqStack &s,char &e) //运算符出栈
{
if (s.top==s.base) //栈为空栈的时候，返回ERROR
{
printf("运算符栈为空!\n");
return ERROR;
}
else
{
e=*--s.top; //栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OK
return OK;
}
}

int StackTraverse(SqStack &s) //运算符栈的遍历
{
char *t;
t=s.base ;
if (s.top==s.base)
{
printf("运算符栈为空!\n"); //栈为空栈的时候返回ERROR
return ERROR;
}
while(t!=s.top)
{
printf(" %c",*t); //栈不为空的时候依次取出栈内元素
t++;
}
return ERROR;
}

//**********************数字栈部分***************************

struct SqStackn //定义数栈
{
int *base; //栈底指针
int *top; //栈顶指针
int stacksize; //栈的长度
};

int InitStackn (SqStackn &s) //建立一个空栈S
{
s.base=(int*)malloc(50*sizeof(int));
if(!s.base)exit(OVERFLOW); //存储分配失败
s.top=s.base;
s.stacksize=50;
return OK;
}

int GetTopn(SqStackn s,int &e) //数栈取栈顶元素

{
if (s.top==s.base)
{
printf("运算数栈为空!\n"); //栈为空的时候返回ERROR
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OK
return OK;
}

int Pushn(SqStackn &s,int e) //数栈入栈
{
if (s.top-s.base >=s.stacksize)
{
printf("运算数栈满!\n"); //栈满的时候，追加5个存储空间

s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) );
if(!s.base) exit (OVERFLOW);

s.top=s.base+s.stacksize; //插入元素e为新的栈顶元素
s.stacksize+=5;
}
*(s.top)++=e; //栈顶指针变化
return OK;
}

int Popn(SqStackn &s,int &e) //数栈出栈
{
if (s.top==s.base)
{
printf(" 运算符栈为空!\n"); //栈为空栈的视时候，返回ERROR

return ERROR;
}
else
{
e=*--s.top; //栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OK
return OK;
}
}

int StackTraversen(SqStackn &s) //数栈遍历

{
int *t;
t=s.base ;
if (s.top==s.base)
{
printf(" 运算数栈为空!\n"); //栈为空栈的时候返回ERROR
return ERROR;
}
while(t!=s.top)
{
printf(" %d",*t); //栈不为空的时候依次输出
t++;
}
return ERROR;
}

//========================================================
// 以下定义函数
//========================================================

int Isoperator(char ch) //判断是否为运算符，分别将运算符和数字进入不同的栈
{
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return 1;
default:
return 0;
}
}

int Operate(int a, char op, int b) //运算操作
{
int result;
switch(op)
{
case '+':
result=a+b;
break;
case '-':
result=a-b;
break;
case '*':
result=a*b;
break;
case '/':
result=a/b;
break;
}
return result;
}

char Precede(char ch1, char ch2) //运算符优先级的比较
{
char p;
switch(ch1)
{
case '+':
case '-':
if (ch2=='+'||ch2=='-'||ch2==')'||ch2=='#')
p = '>'; //ch1运算符的优先级小于ch2运算符
else
p = '<';
break;

case '*':
case '/':
if (ch2 == '(')
p = '<';
else
p = '>';
break;

case '(':
if (ch2 == ')')
p = '=';
else if (ch2 == '#')
{
printf(" 表达式错误!运算符不匹配!\n") ;
exit(0);
}
else
p = '<';
break ;

case ')':
if (ch2 == '(')
{
printf(" 表达式错误!运算符不匹配!\n") ;
exit(0);
}
else
p = '>';
break ;

case '#':
if (ch2 == ')')
{
printf(" 表达式错误!运算符不匹配!\n") ;
exit(0);
}
else if (ch2 == '#')
p = '=';
else
p='<';
break;
}
return p;
}

//========================================================
// 以下是求值过程
//========================================================
int EvaluateExpression() //参考书p53算法3.4
{
int a, b, temp, answer;
char ch,op,e;
char *str;
int j = 0;
SqStackn OPND; //OPND为运算数字栈
SqStack OPTR; //OPTR为运算符栈
InitStack(OPTR);
Push(OPTR,'#'); //,所以此栈底是'#'，因为运算符栈以'#'作为结束标志
InitStackn(OPND);

// printf("\n\n按任意键开始求解:\n\n");
// ch=getch();
printf("\n请输入表达式并以'#'结束:\n");
str =(char*)malloc(50*sizeof(char));
gets(str);
ch=str[j]; //ch是字符型的，而e是整型的整数
j++;

GetTop(OPTR,e); //e为栈顶元素返回值

while (ch!='#' || e!='#')
{
if (!Isoperator(ch)) //遇到数字,转换成十进制并计算
{
temp=ch-'0'; //将字符转换为十进制数
ch=str[j];
j++;
while(!Isoperator(ch))
{
temp=temp*10 + ch-'0'; //将逐个读入运算数的各位转化为十进制数
ch=str[j];
j++;
}
Pushn(OPND,temp);
}

else if (Isoperator(ch)) //判断是否是运算符,不是运算符则进栈

switch (Precede(e,ch))
{
case '<' : Push(OPTR,ch); // 栈顶元素优先权低
ch = str[j++];
printf("\n\n 运算符栈为：\n"); //输出栈，显示栈的变化
StackTraverse(OPTR);
printf("\n 运算数栈为：\n");
StackTraversen(OPND);
break;
case '=' : Pop(OPTR,op); // 脱括号并接收下一字符
ch = str[j++] ;
printf("\n\n 运算符栈为：\n");
StackTraverse(OPTR);
printf("\n 数栈为：\n");
StackTraversen(OPND);
break;
case '>' : Pop(OPTR,op); //弹出最上面两个，并运算，把结果进栈
Popn(OPND,b);
Popn(OPND,a);
Pushn(OPND,Operate(a,op,b));
printf("\n\n 运算符栈为：\n");
StackTraverse(OPTR);
printf("\n 数栈为：\n");
StackTraversen(OPND);
}
else
{
printf("您的输入有问题，请检查重新输入!");
exit(0);
}

GetTop(OPTR,e); //取出运算符栈最上面元素是否是'#'

} //while
GetTopn(OPND,answer); //已输出。数字栈最上面即是最终结果
return answer;
}

//========================================================
// 执行部分
//========================================================
void ShowMenu()
{
printf("\n\n");
printf("███████████████████████████████████████\n");
printf("██ ██\n");
printf("██ 表达式求值系统 ██\n");
printf("██ ██\n");
printf("███████████████████████████████████████\n");
}
void Quit();
void Manage()
{
int answer;
// ShowMenu();
answer=EvaluateExpression();
printf("\n\n表达式结果是: %d\n",answer);
Quit();
}
void Quit()
{
char ch;
printf(" 本次运算结束。\n");
printf(" 继续本系统吗？\n\n");
printf(" 继续运算请按Y/y ");
printf("\n 退出程序请按N/n ");
printf(" \n___________________________________________________________________\n");

ch=getch();
ch=toupper(ch); //将ch字符转换成大写字母

if(ch == 'N')
{
printf("\n\n 系统退出。\n");
exit(0);
}
Manage();
}

int main()
{
ShowMenu();
Manage();
return 0;
}

感想体会与总结
好的算法＋编程技巧＋高效率＝好的程序。
1、 做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。
2、 做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。
3、 感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。
4、 通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。

PHP正则表达式的快速学习方法
1、入门简介
简单的说，正则表达式是一种可以用于模式匹配和替换的强有力的工具。我们可以在几乎所有的基于UNIX系统的工具中找到正则表达式的身影，例如，vi编辑器，Perl或PHP脚本语言，以及awk或sed shell程序等。此外，象JavaScript这种客户端的脚本语言也提供了对正则表达式的支持。由此可见，正则表达式已经超出了某种语言或某个系统的局限，成为人们广为接受的概念和功能。正则表达式可以让用户通过使用一系列的特殊字符构建匹配模式，然后把匹配模式与数据文件、程序输入以及WEB页面的表单输入等目标对象进行比较，根据比较对象中是否包含匹配模式，执行相应的程序。　　举例来说，正则表达式的一个最为普遍的应用就是用于验证用户在线输入的邮件地址的格式是否正确。如果通过正则表达式验证用户邮件地址的格式正确，用户所填写的表单信息将会被正常处理；反之，如果用户输入的邮件地址与正则表达的模式不匹配，将会弹出提示信息，要求用户重新输入正确的邮件地址。由此可见正则表达式在WEB应用的逻辑判断中具有举足轻重的作用。
2、基本语法
在对正则表达式的功能和作用有了初步的了解之后，我们就来具体看一下正则表达式的语法格式。
(1)正则表达式的形式一般如下：/love/其中位于“/”定界符之间的部分就是将要在目标对象中进行匹配的模式。用户只要把希望查找匹配对象的模式内容放入“/”定界符之间即可。
(2)为了能够使用户更加灵活的定制模式内容，正则表达式提供了专门的“元字符”。所谓元字符就是指那些在正则表达式中具有特殊意义的专用字符，可以用来规定其前导字符（即位于元字符前面的字符）在目标对象中的出现模式。较为常用的元字符包括： “+”， “*”，以及 “?”。其中，“+”元字符规定其前导字符必须在目标对象中连续出现一次或多次，“*”元字符规定其前导字符必须在目标对象中出现零次或连续多次，而“?”元字符规定其前导对象必须在目标对象中连续出现零次或一次。下面，就让我们来看一下正则表达式元字符的具体应用。
/fo+/因为上述正则表达式中包含“+”元字符，表示可以与目标对象中的 “fool”, “fo”, 或者 “football”等在字母f后面连续出现一个或多个字母o的字符串相匹配。
/eg*/因为上述正则表达式中包含“*”元字符，表示可以与目标对象中的 “easy”, “ego”, 或者 “egg”等在字母e后面连续出现零个或多个字母g的字符串相匹配。
/Wil?/因为上述正则表达式中包含“？”元字符，表示可以与目标对象中的 “Win”, 或者 “Wilson”,等在字母i后面连续出现零个或一个字母l的字符串相匹配。除了元字符之外，用户还可以精确指定模式在匹配对象中出现的频率。例如，
/jim{2,6}/上述正则表达式规定字符m可以在匹配对象中连续出现2-6次，因此，上述正则表达式可以同jimmy或jimmmmmy等字符串相匹配。在对如何使用正则表达式有了初步了解之后，我们来看一下其它几个重要的元字符的使用方式。\s：用于匹配单个空格符，包括tab键和换行符；\S：用于匹配除单个空格符之外的所有字符；\d：用于匹配从0到9的数字；\w：用于匹配字母，数字或下划线字符；\W：用于匹配所有与\w不匹配的字符；. ：用于匹配除换行符之外的所有字符。（说明：我们可以把\s和\S以及\w和\W看作互为逆运算）下面，我们就通过实例看一下如何在正则表达式中使用上述元字符。
/\s+/上述正则表达式可以用于匹配目标对象中的一个或多个空格字符。
/\d000/如果我们手中有一份复杂的财务报表，那么我们可以通过上述正则表达式轻而易举的查找到所有总额达千元的款项。
(3)除了我们以上所介绍的元字符之外，正则表达式中还具有另外一种较为独特的专用字符，即定位符。定位符用于规定匹配模式在目标对象中的出现位置。较为常用的定位符包括：“^”, “$”, “\b” 以及 “\B”。其中，“^”定位符规定匹配模式必须出现在目标字符串的开头，“$”定位符规定匹配模式必须出现在目标对象的结尾，\b定位符规定匹配模式必须出现在目标字符串的开头或结尾的两个边界之一，而“\B”定位符则规定匹配对象必须位于目标字符串的开头和结尾两个边界之内，即匹配对象既不能作为目标字符串的开头，也不能作为目标字符串的结尾。同样，我们也可以把“^”和“$”以及“\b”和“\B”看作是互为逆运算的两组定位符。举例来说：
/^hell/因为上述正则表达式中包含“^”定位符，所以可以与目标对象中以 “hell”, “hello”或 “hellhound”开头的字符串相匹配。
/ar$/因为上述正则表达式中包含“$”定位符，所以可以与目标对象中以 “car”, “bar”或 “ar” 结尾的字符串相匹配。
/\bbom/因为上述正则表达式模式以“\b”定位符开头，所以可以与目标对象中以 “bomb”, 或 “bom”开头的字符串相匹配。
/man\b/因为上述正则表达式模式以“\b”定位符结尾，所以可以与目标对象中以 “human”, “woman”或 “man”结尾的字符串相匹配。
(4)为了能够方便用户更加灵活的设定匹配模式，正则表达式允许使用者在匹配模式中指定某一个范围而不局限于具体的字符。例如：
/[A-Z]/上述正则表达式将会与从A到Z范围内任何一个大写字母相匹配。
/[a-z]/上述正则表达式将会与从a到z范围内任何一个小写字母相匹配。
/[0-9]/上述正则表达式将会与从0到9范围内任何一个数字相匹配。
/([a-z][A-Z][0-9])+/上述正则表达式将会与任何由字母和数字组成的字符串，如 “aB0” 等相匹配。这里需要提醒用户注意的一点就是可以在正则表达式中使用 “()” 把字符串组合在一起。“()”符号包含的内容必须同时出现在目标对象中。因此，上述正则表达式将无法与诸如“abc”等的字符串匹配，因为“abc”中的最后一个字符为字母而非数字。
(5)如果我们希望在正则表达式中实现类似编程逻辑中的“或”运算，在多个不同的模式中任选一个进行匹配的话，可以使用管道符 “|”。例如：
/to|too|2/上述正则