数据结构课程设计----表达式求值

概述本文章向大家介绍数据结构课程设计----表达式求值，主要包括数据结构课程设计----表达式求值使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

表达式求值问题         给定一个四则运算的中缀表达式，编程计算表达式的值。

基本要求：    

（1）在给定的表达式中要包含括号；    

（2）栈的 *** 作要求自己完成，不允许调用类库中的方法；    

（3）对不同的 *** 作编写相应的函数。

测试数据要求：         给定测表达式（字符串）中的数字字符要有包含两位以上的数字字符。

/***********************************************************************************************

***

第七题 算术表达式求值

[问题描述 ]

一个算术表达式是由 *** 作数 (operand) 、运算符 (operator) 和界限符 (delimiter) 组成的。

假设 *** 作数是正整数，

运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符 “#，

”

如：#（7+15）*（23-28/4 ）#。引入表达式起始、结束符是为了方便。

编程利用 “算符优先法 ”求算术表达式的值。

[基本要求 ]

（1） 从键盘读入一个合法的算术表达式，输出正确的结果。

（2） 显示输入序列和栈的变化过程。

************************************************************************************************

***/

#include

#include

#include

#include

#include

#include

#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("nn 按任意键开始求解 :nn");

// 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("nn 运算符栈为： n"); //输出栈，显示栈的变化

StackTraverse(OPTR);

printf("n 运算数栈为： n");

StackTraversen(OPND);

break;

case '=' : Pop(OPTR,op); // 脱括号并接收下一字符

ch = str[j++] ;

printf("nn 运算符栈为： n");

StackTraverse(OPTR);

printf("n 数栈为： n");

StackTraversen(OPND);

break;

case '>' : Pop(OPTR,op); //d出最上面两个，并运算，把结果进栈

Popn(OPND,b);

Popn(OPND,a);

Pushn(OPND,Operate(a,b));

printf("nn 运算符栈为： n");

StackTraverse(OPTR);

printf("n 数栈为： n");

StackTraversen(OPND);

}

else

{

printf(" 您的输入有问题，请检查重新输入 !");

exit(0);

}

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

} //while

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

return answer;

}

//========================================================

// 执行部分

//========================================================

voID ShowMenu()

{

printf("nn");

printf(" 表达式求值系统 n");

}

voID Quit();

voID Manage()

{

int answer;

// ShowMenu();

answer=EvaluateExpression();

printf("nn 表达式结果是 : %dn",answer);

Quit();

}

voID Quit()

{

char ch;

printf(" 本次运算结束。 n");

printf(" 继续本系统吗？ nn");

printf(" 继续运算请按 Y/y ");

printf("n 退出程序请按 N/n ");

printf("n___________________________________________________________________n");

ch=getch();

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

if(ch == 'N')

{

printf("nn 系统退出。 n");

exit(0);

}

Manage();

}

int main()

{

ShowMenu();

Manage();

return 0;

}

总结

以上是内存溢出为你收集整理的数据结构课程设计----表达式求值全部内容，希望文章能够帮你解决数据结构课程设计----表达式求值所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。