数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]此函数功能为:读取算数表达式,对表达式中的数字压入数字栈,操作符压入操作符栈,然后对操作符处理并且判断,然后通过选择进行表达式的计算并输出中间运算结果

  1. 需求分析
    1. 问题的提出

c或c++语言编写程序实现表达式求值,即验证某算术表达式的正确性,若正确,则计算该算术表达式的值。表达式从键盘输入后,按以下方法对该表达式中成份逐个进行分析:

1)若是数字,则判断该数字的合法性。若合法,则压入数据到堆栈中。

2)若是规定的运算符,则根据规则进行处理。在处理过程中,将计算该表达式的值。

3)若是其它字符,则返回错误信息。

若上述处理过程中没有发现错误,则认为该表达式合法,并打印处理结果。

    1. 任务与分析
      1. 任务要求

  用栈数据结构实现,且程序中应主要编写如下几个功能函数:

 void initstack():初始化栈。

 int Make_str():语法检查并计算。

 int push_operate(int operate):将操作码压入堆栈。

 int push_num(double num):将操作数压入堆栈。

 int procede(int operate):处理操作码。

 int change_opnd(int operate):将字符型操作码转换成优先级。

 int push_opnd(int operate):将操作码压入堆栈。

 int pop_opnd():将操作码弹出堆栈。

 int caculate(int cur_opnd):简单计算+,-,*,/,(,)。

 double pop_num():弹出操作数。

      1. 任务分析

需要对操作符进行判断,借助堆栈数据结构来对数据和操作符进行储存和保护,然后进行简单的加减乘除和括号运算,并且使用double型对数据进行运算。

  1. 程序运行平台

采用dev c++ 5.11进行程序的实现

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  1. 概要设计
    1. 主程序函数调用逻辑,和流程图

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  1. 详细设计
    1. 详细设计思想
  1. 遇到数字,则用第二个指针将该数字读取出来,然后push到num中
  2. 遇到(,直接push到操作符栈中
  3. 遇到),则从ops中逐一弹出操作符直到遇到(,每弹出一个操作符,就通过count函数计算一遍该操作符计算出的值,再将该值压入栈
  4. 遇到+、-、*、/,那么就通过while循环检查是否ops栈顶优先级大于等于当前操作符,若满足,则弹出栈顶操作符,计算值;最后将当前操作符压入操作符栈。
  5. 转换过程需要用到栈,具体过程如下:
  6. 如果遇到操作数,我们就直接将其输出。
  7. 如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。
  8. 如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。
  9. 如果遇到任何其他的操作符,如(+, *,()等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到)的情况下我们才弹出(,其他情况我们都不会弹出(。
  10. 如果我们读到了输入的末尾,则将栈中所有元素依次弹出。
    1. 具体运算实例

    1. 本程序定义的数据结构
      1. 静态结构

1数据栈的结构体定义

typedef struct {
//定义操作数栈

double num[NUM_Size];//定义数值栈的大小

int top;//设置数值栈的栈指针

} num_stack;

2操作符栈结构体定义

typedef  char operate;//操作符元素类型

typedef struct {
//定义操作码栈

operate str[NUM_Size] ;//定义操作符栈的存放数组大小

int top;//定义栈指针

} operate_stack;

      1. 动态结构

1操作数栈的结构定义

typedef struct{
//操作数栈结构定义

    double *basics;

    double *top;

    int stacksize;

}OpndStack;

2操作符栈的结构定义

typedef struct{
//操作符栈结构定义

    char *basics;

    char *top;

    int stacksize;

}OptrStack;

  1. 静态栈
  • 操作符栈初始化

void InitStack_operate(operate_stack*s)// operate_stack*s是操作符栈

{
//构造一个空栈S

s->top = -1;

}

  • 操作数栈

void InitStack_num(num_stack*S) {

//构造一个空栈S

S->top = -1;

}

2动态栈

  • 操作符栈

int InitStack_OPTR(OptrStack *S){

    //构造一个空操作数栈S

    S->basics=(char *)malloc(sizeof(char));

    if(!S->basics)//分配失败

    {

        printf(“分配内存失败.\n”);

        exit(0);

    }

    S->top=S->basics;

    S->stacksize=STACK_INIT_SIZE;

    return OK;

}

  • 操作数栈

int InitStack_num(OpndStack *S){

    //构造一个空操作数栈S

    S->basics=(double *)malloc(sizeof(double));

    if(!S->basics)//分配失败

    {

        printf(“分配内存失败.\n”);

        exit(0);

    }

    S->top=S->basics;

    S->stacksize=STACK_INIT_SIZE;

    return OK;

}

      1. 语法检查和计算

1.首先对函数名分析

int Make_str可以看出函数名需要返回一个int类型的值,检查类型的函数要反馈结果,为判断正确和错误需要设置返回TRUE和FALSE为就解决问题,对程序进行宏定义如下:

#define TRUE     1

#define FALSE    0

正确返回1,否则返回0。

2.其次功能而言

需要函数对操作符的判断这里我只将算数表达式中的操作符判断出来,算数表达式输入错误的功能将放到对数据栈处理函数中去;实际此函数功能只设置了判断 +、-、*、/、(、),这几个符号,假如是这几个符号返回TURE否则返回FALSE。

int Make_str(char c) {

//判断c是否是一个运算操作符

switch(c) {

case ‘+’:

case ‘-‘:

case ‘*’:

case ‘/’:

case ‘(‘:

case ‘)’:

case ‘#’:

return TRUE;

break;

default:

return FALSE;

break;

}

}

(函数功能单一不再附上流程图)

      1. 将操作码压入堆栈

1.压栈流程图

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

2 .因为仅能从函数名进行线索的提取,首先对函数名分析

int push_operate(int operate):将操作码压入堆栈,需要返回一个int类型的值,所以压栈成功返回TRUE否则返回FALSE.

3此段代码如下

  • 静态结构下

int  push_operate(operate_stack*s,operate x) { //操作符入栈函数

if (s->top == NUM_Size-1) return(FALSE);/*栈已满*/

s->top++;//修改栈顶指针

s->str[s->top] = x;//x进栈

return(TRUE);

}

  • 动态站结构下

int Push_OPTR(OptrStack *S,char e){

    //插入元素e为新的栈顶元素

    if(S->top-S->basics>=S->stacksize){
//栈已满,追加存储空间

        S->basics=(char *)realloc(S->basics,(S->stacksize+STACKINCREMENT)*sizeof(char));

        if(!S->basics)

        {

            printf(“重新申请空间失败.\n”);

            exit(0);

        }

        S->top=S->basics+S->stacksize;//更改栈顶指针

        S->stacksize+=STACKINCREMENT;

    }

    *S->top++=e;

    return OK;

}

      1. 将操作数压入堆栈。

流程图和操作符压栈基本一致

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

详细代码如下

  • 静态结构下

int push_num(num_stack*S,double x) {

if (S->top == NUM_Size-1) return(FALSE);/*栈已满*/

S->top++;//修改栈顶指针

S->num[S->top] = x;//x进栈

return(TRUE);

}

  • 动态栈下

int push_num(OpndStack *S,double e){

    //插入元素e为新的栈顶元素

    if(S->top-S->basics>=S->stacksize){
//栈已满,追加存储空间

       S->basics=(double *)realloc(S->basics,(S->stacksize+STACKINCREMENT)*sizeof(double));

       if(!S->basics)

        {

            printf(“重新申请空间失败.\n”);

            exit(0);

        }

        S->top=S->basics+S->stacksize;//更改栈顶指针

        S->stacksize+=STACKINCREMENT;

    }

    *S->top++=e;

    return OK;

}

      1. 处理操作码
  1. 此函数功能为:读取算数表达式,对表达式中的数字压入数字栈,操作符压入操作符栈,然后对操作符处理并且判断,然后通过选择进行表达式的计算并输出中间运算结果。

流程图如下:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

代码如下:

double procede(const char *expression) {

//对只有四则运算符的算数表达式 expression 求值

//OPTR:操作符栈,OPND:操作数栈

const char *c=expression;

operate_stack   OPTR;//操作符栈

num_stack       OPND;//操作数栈

char x,opnd;

char get,ch;

double result;

double a,b,num;

InitStack_operate(&OPTR);//初始化操作符栈

InitStack_num(&OPND);//初始化操作数栈

push_operate(&OPTR,’#’);//首先将匹配符号’#’入栈

GetTop_operate(&OPTR,&get);

while(*c!=’#’||get!=’#’) {

GetTop_operate(&OPTR,&get);

//printf(“getchar=%c\n”,*c);

if(*c==’\0′)//遇到回车退出

break;

if(FALSE==Make_str(*c)) {

c=getOpnd(c,&num);//取出新的操作符,并处理数字

push_num(&OPND,num);

} else

switch(change_opnd(get,*c)) {

case ‘<‘:

push_operate(&OPTR,*c);

c++;

break;

case ‘=’:

pop_opnd(&OPTR,&x);

c++;

break;

case ‘>’:

pop_opnd(&OPTR,&opnd);

pop_num(&OPND,&b);

pop_num(&OPND,&a);

result=caculate(a,opnd,b);

//printf(“temp result is:%d\n”,result);

push_num(&OPND,result);

break;

default:

break;

}//switch

}//while

GetTop_num(&OPND,&result);

return result;

}

      1. 将字符型操作码转换成优先级

1从函数名来看char change_opnd(char one,char two),此函数功能为将两个操作符优先级进行比较,然后返回两个操作符的优先级情况具体流程图如下:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  • 先将代码放在这里

char change_opnd(char,char op2){

    //判断op1和op2优先级的高低,返回’>’,'<‘,’=’

    switch(op1){

        case ‘+’:

            switch(op2){

                case ‘*’:

                case ‘/’:

                case ‘(‘:

                       return ‘<‘;//加号的优先级低于*/(的优先级

                       break;

                default:

                    return ‘>’;

                    break;

            }

            break;

        case ‘-‘:

            switch(op2){

                case ‘*’:

                case ‘/’:

                case ‘(‘:

                       return ‘<‘;

                       break;

                default:

                    return ‘>’;

                    break;

            }

            break;

        case ‘*’:

            switch(op2){

                case ‘(‘:

                       return ‘<‘;

                       break;

                default:

                    return ‘>’;

                    break;

            }

            break;

        case ‘/’:

            switch(op2){

                case ‘(‘:

                       return ‘<‘;

                       break;

                default:

                    return ‘>’;

                    break;

            }

            break;

        case ‘(‘:

            switch(op2){

                case ‘)’:

                    return ‘=’;

                    break;

                default:

                    return ‘<‘;

                    break;

            }

            break;

        case ‘)’:

            switch(op2){

                default:

                    return ‘>’;

                    break;

            }

            break;

        case ‘#’:

            switch(op2){

                case ‘#’:

                    return ‘=’;

                    break;

                default:

                    return ‘<‘;

                    break;

            }

            break;

        default:

            return ‘<‘;

            break;

    }

}

      1. 将操作码弹出堆栈
  • 还是先从函数名来分析int pop_opnd()需要返回值,要体现出栈成功的过程当出栈成功返回TURE否则返回FALSE.
  • 流程图如下:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  • 此段代码如下

静态栈结构下的代码

int pop_opnd(operate_stack*s,operate*x) { //将操作码弹出堆栈

if(s->top == -1)//栈为空

return(FALSE);

else {

*x= s->str[s->top];//栈顶元素赋给x

s->top–;//修改栈顶指针

return(TRUE);

}

}

动态栈结构下的代码

int pop_opnd(OptrStack *S,char *e){

    //若栈S不为空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR

    if(S->top==S->basics){//栈为空

        printf(“栈为空.\n”);

        return ERROR;

    }

    *e=*(–S->top);

    return OK;

}

      1. 简单计算+,-,*,/,(,)
  • 此函数在接收了两个double型参数和一个操作符后运用switch,case功能进行对中间子运算表达式进行运算并且显示过程计算。
  • 代码功能单一不做流程图展示
  • 为理解代码含义对代码进行注释以便理解。如下:

double caculate(double a,char opnd,double b){

    //对操作数a,b进行opnd运算,并返回运算结果

    //opnd只能是四则运算符号

    double temp;

    switch(opnd){

        case ‘+’:

            temp=a+b;

            break;

        case ‘-‘:

            temp=a-b;

            break;

        case ‘*’:

            temp=a*b;

            break;

        case ‘/’:

            if(b==0){

                printf(“错误:除数为0.”);

                exit(0);

            }

            temp=a/b;

            break;

        default:

            printf(“没有此操作符.\n”);

            break;

    }

    printf(“%f %c %f = %f\n”,a,opnd,b,temp);

    return temp;

}

      1. 弹出操作数
  • 出栈和进栈功能相似,栈为空返回TURE否则返回FALSE
  • 数据出栈流程图如下:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  • 静态栈结构数出栈代码

int pop_num(num_stack*S,double*x) {

if(S->top == -1)//栈为空

return(FALSE);

else {

*x= S->num[S->top];//栈顶元素赋给x

S->top–;//修改栈顶指针

return(TRUE);

}

}

  • 动态栈数据出栈

int pop_num(OpndStack *S,double *e){

    //若栈S不为空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR

    if(S->top==S->basics){
//栈为空

        printf(“栈为空.\n”);

        return ERROR;

    }

    *e=*(–S->top);

    return OK;

}

    1. 附加处理函数
      1. 进栈取符函数

分析:

  • 首先读取算数表达式读到数字处理数字,读到操作符停止处理数字,将处理好的数字存放在num中,并且返回当前指针所指的操作符。
  • 将读取的数字字符串进行处理:
  • 整数部分,读到一个数*10存到num2中再读取一个数字num2*10加当前数字,循环直到读到小数点和操作符结束。
  • 小数部分,对循环次数记录在k中,读到一个数用middle*0.1k数据结构栈c语言代码_c++数据结构与算法[通俗易懂]乘以当前数字,循环直到读到操作符结束。
  • 在对当前数字进行操作时遇到非法字符则报告错误且结束整个函数。

流程图:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

代码如下

const char *getOpnd(const char *c,double *op) {

//获得以*c开始的操作数,返回后c为操作符

double sum=0,tmp1,tmp2,sum1=0,sum2=0,middle=0.1;

/* sum1用来存放小数点后的数字;sum2用来存放小数点前的函数;sum用来

存放整体操作数;tmp1,tmp2用来处理中间值。

int k;

while(FALSE==Make_str(*c)) {

if(*c==’.’) {

c++;

while(FALSE==Make_str(*c)) {

int i=0;

tmp1=*c-‘0’;

sum1=tmp1*middle+sum1;

if(tmp1<0||tmp1>9) {

printf(“表达式错误无法计算!.”);

exit(0);

}

i++;

for(k=1;k<=i;k++){

middle=middle*0.1;

}

//printf(“sum1=%f\n”,sum1);

c++;

}

} else {

while(FALSE==Make_str(*c)&&*c!=’.’) {

tmp2=*c-‘0’;

sum2=sum2*10+tmp2;

//printf(“tmp=%d\n”,tmp);

if(tmp2<0||tmp2>9) {

printf(“表达式错误无法计算!.”);

exit(0);

}

c++;

}

}

}

 sum=sum1+sum2;

*op=sum;

//rintf(“getOpnd:%f\n”,*op);

return c;

      1. 表达式处理函数

函数功能:遍历字符串遇到空格删除同过指针进行覆盖式删除

详细代码如下:

void Standard(char *expression){

    //将字符串表达式标准化为算术表达式

    char *p=expression,*q;

    while(*p!=’\0′){
//遍历字符串

        if(*p==’ ‘){
//如果是空格,删除

            q=p;//指针地址赋值

            do{

                *q=*(q+1);

                q++;

            }while(*q!=’\0′);

        }

        p++;

    }

    *p++=’#’;

    *p=’\0′;

}

  1. 调试分析
    1. 所遇问题
  • 遇到的困难1

问题描述:无法判定除运算符以外非数字字符,假如用户输入除了数字和操作符的字符,该字符会转换为ASCII码当成数字来处理,错误代码如下:仅仅只能判断操作符。

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

如果输入小数,小数据点也会如上所示一般转换为ASCII码来进行运算

初步解决如下:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

但是在debug时发现if函数不起作用,在分析时发现问题:tmp<0和>9在逻辑上根本无法发生,应该用或语句来判别

解决方法如下:加入一个if语句来解决表达式输入错误

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

该操作目的:假如在处理数字时遇到非数字字符则函数整体结束

  • 问题2

问题描述:小数部分无法处理,会将小数点当作运算数来解决无法运算小数问题

原始代码如下

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

解决方法:将小数部分和整数部分分开来解决,用if语句来分支,两分支中各设立一个while循环来进行数字处理

    整数部分,读到一个数*10存到num2中再读取一个数字num2*10加当前数字,循环直到读到小数点和操作符结束。

    小数部分,对循环次数记录在k中,读到一个数用middle*0.1k数据结构栈c语言代码_c++数据结构与算法[通俗易懂]乘以当前数字,循环直到读到操作符结束。

在对当前数字进行操作时遇到非法字符则报告错误且结束整个函数。

具体体现:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

    1. 算法的空间分析

1本程序使用两个栈和一个存放表达式的节点空间

2用数组来完成栈的实现,需要提前设定好数组大小,无论你是否需要,空间大小已经占用了,不太节省空间

  • 改进如下:

重新写一个以动态栈结构的程序,当需要存储时申请一个节点来储存数据,所以我将改进的动态栈程序源代码,附在附录中。

  1. 测试结果

1用户输入界面

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

2假如输入错误的表达式:

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

2输入表达式:3.25+4.65/(36.21-55.65)*3.0

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

3简单表达式运算(为方便理解)

数据结构栈c语言代码_c++数据结构与算法[通俗易懂]

  1. 用户说明
  • 函数功能

1只可以对+-*/()符号进行运算

2可以进行小数的运算

  • 注意

1要输入正确的表达式,否则会终止程序。

  1. 结论

设计体会和收获:

  • 发现自己也能解决有点复杂的问题,程序设计思想上有了很大的提高,学会了仔细分析问题的关键和辅助功能,在应用上设计程序要符合大众化的思维方式
  • 因为时间问题,只能做出表达式基本运算,在以后的时间里,我会改善这个计算程序,让它能计算更复杂的表达式,如加上 sin , cos 时的运算。

整代码:

动态地址分配:

#include <stdio.h>
#include <stdlib.h>
#define OK      1
#define ERROR   0
#define TRUE    1
#define FALSE   0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define BUFFERSIZE 256
typedef struct { //操作数栈结构定义
	double *basics;
	double *top;
	int stacksize;
} OpndStack;
//操作符元素类型
typedef struct { //操作符栈结构定义
	char *basics;
	char *top;
	int stacksize;
} OptrStack;
void Standard(char *expression);
//将表达式标准化
double procede(const char *expression);
//算数表达式求值
int Make_str(char c);
//判断c是否是一个操作符
char change_opnd(char op1,char op2);
//判断op1和op2优先级的高低,返回'>','<','='
double caculate(double a,char opnd,double b);
//对操作数a,b进行opnd运算
const char *getOpnd(const char *c,double *op);
//获得以*c开始的操作数,返回后c为操作符
//==========操作数栈===========//
int InitStack_num(OpndStack *S) {
	//构造一个空操作数栈S
	S->basics=(double *)malloc(sizeof(double));
	if(!S->basics) { //分配失败
		printf("分配内存失败.\n");
		exit(0);
	}
	S->top=S->basics;
	S->stacksize=STACK_INIT_SIZE;
	return OK;
}
int GetTop_num(OpndStack S,double *e) {
	//若操作数栈不为空,则用e返回S的栈顶元素,并返回OK;否则返回FALSE
	if(S.top==S.basics) {
		printf("栈为空.\n");
		return FALSE;
	} else {
		*e=*(S.top-1);
		return OK;
	}
}
int push_num(OpndStack *S,double e) {
	//插入元素e为新的栈顶元素
	if(S->top-S->basics>=S->stacksize) { //栈已满,追加存储空间
		S->basics=(double *)realloc(S->basics,(S->stacksize+STACKINCREMENT)*sizeof(double));
		if(!S->basics) {
			printf("重新申请空间失败.\n");
			exit(0);
		}
		S->top=S->basics+S->stacksize;//更改栈顶指针
		S->stacksize+=STACKINCREMENT;
	}
	*S->top++=e;
	return OK;
}

int pop_num(OpndStack *S,double *e) {
	//若栈S不为空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR
	if(S->top==S->basics) { //栈为空
		printf("栈为空.\n");
		return ERROR;
	}
	*e=*(--S->top);
	return OK;
}

//==========操作符栈===========//
int InitStack_OPTR(OptrStack *S) {
	//构造一个空操作数栈S
	S->basics=(char *)malloc(sizeof(char));
	if(!S->basics) { //分配失败
		printf("分配内存失败.\n");
		exit(0);
	}
	S->top=S->basics;
	S->stacksize=STACK_INIT_SIZE;
	return OK;
}

char GetTop_OPTR(OptrStack S) {
	//若操作数栈不为空,则返回S的栈顶元素,并返回OK;否则返回FALSE
	char e;
	if(S.top==S.basics) {
		printf("栈为空.\n");
	} else {
		e=*(S.top-1);
	}
	return e;
}

int Push_OPTR(OptrStack *S,char e) {
	//插入元素e为新的栈顶元素
	if(S->top-S->basics>=S->stacksize) { //栈已满,追加存储空间
		S->basics=(char *)realloc(S->basics,(S->stacksize+STACKINCREMENT)*sizeof(char));
		if(!S->basics) {
			printf("重新申请空间失败.\n");
			exit(0);
		}
		S->top=S->basics+S->stacksize;//更改栈顶指针
		S->stacksize+=STACKINCREMENT;
	}
	*S->top++=e;
	return OK;
}

int pop_opnd(OptrStack *S,char *e) {
	//若栈S不为空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR
	if(S->top==S->basics) { //栈为空
		printf("栈为空.\n");
		return ERROR;
	}
	*e=*(--S->top);
	return OK;
}

//============运算操作================//
double procede(const char *expression) {
	//对只有四则运算符的算数表达式 expression 求值
	//OPTR:操作符栈,OPND:操作数栈
	const char *c=expression;
	OpndStack OPND;
	OptrStack OPTR;
	char x,opnd;
	double a,b,num,result;
	InitStack_OPTR(&OPTR);//初始化操作符栈
	InitStack_num(&OPND);//初始化操作数栈
	Push_OPTR(&OPTR,'#');//首先将匹配符号'#'入栈
	while(*c!='#'||GetTop_OPTR(OPTR)!='#') {
		//printf("getchar=%c\n",*c);
		if(*c=='\0')//遇到回车退出
			break;
		if(FALSE==Make_str(*c)) {
			c=getOpnd(c,&num);
			push_num(&OPND,num);
		} else
			switch(change_opnd(GetTop_OPTR(OPTR),*c)) {
				case '<':
					Push_OPTR(&OPTR,*c);
					c++;
					break;
				case '=':
					pop_opnd(&OPTR,&x);
					c++;
					break;
				case '>':
					pop_opnd(&OPTR,&opnd);
					pop_num(&OPND,&b);
					pop_num(&OPND,&a);
					//printf("a:%f\n",a);
					result=caculate(a,opnd,b);
					//printf("temp result is:%f\n",result);
					push_num(&OPND,result);
					break;
				default:
					//printf("change_opnd:%c",change_opnd(GetTop_OPTR(OPTR),*c));
					break;
			}//switch
	}//while
	GetTop_num(OPND,&result);
	return result;
}

void Standard(char *expression) {
	//将字符串表达式标准化为算术表达式
	char *p=expression,*q;
	while(*p!='\0') { //遍历字符串
		if(*p==' ') { //如果是空格,删除
			q=p;
			do {
				*q=*(q+1);
				q++;
			} while(*q!='\0');
		}
		p++;
	}
	*p++='#';
	*p='\0';
}
const char *getOpnd(const char *c,double *op) {
//获得以*c开始的操作数,返回后c为操作符
	double sum=0,tmp1,tmp2,sum1=0,sum2=0,middle=0.1;
	int k;
	while(FALSE==Make_str(*c)) {
		if(*c=='.') {
			c++;
			while(FALSE==Make_str(*c)) {
				int i=0;
				tmp1=*c-'0';
				sum1=tmp1*middle+sum1;
				if(tmp1<0||tmp1>9) {
					printf("表达式错误无法计算!.");
					exit(0);
				}
				i++;
				for(k=1; k<=i; k++) {
					middle=middle*0.1;
				}
//printf("sum1=%f\n",sum1);
				c++;
			}
		} else {
			while(FALSE==Make_str(*c)&&*c!='.') {
				tmp2=*c-'0';
				sum2=sum2*10+tmp2;
//printf("tmp=%d\n",tmp);
				if(tmp2<0||tmp2>9) {
					printf("表达式错误无法计算!.");
					exit(0);
				}
				c++;
			}
		}
	}
	sum=sum1+sum2;
	*op=sum;
//rintf("getOpnd:%f\n",*op);
	return c;
}
int Make_str(char c) {
	//判断c是否是一个运算操作符
	switch(c) {
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '#':
			return TRUE;
			break;
		default:
			return FALSE;
			break;
	}
}

char change_opnd(char one,char two) {
	//判断op1和op2优先级的高低,返回'>','<','='
	switch(one) {
		case '+':
			switch(two) {
				case '*':
				case '/':
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
			}
			break;
		case '-':
			switch(two) {
				case '*':
				case '/':
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
			}
			break;
		case '*':
			switch(two) {
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
			}
			break;
		case '/':
			switch(two) {
				case '(':
					return '<';
					break;
				default:
					return '>';
					break;
			}
			break;
		case '(':
			switch(two) {
				case ')':
					return '=';
					break;
				default:
					return '<';
					break;
			}
			break;
		case ')':
			switch(two) {
				default:
					return '>';
					break;
			}
			break;
		case '#':
			switch(two) {
				case '#':
					return '=';
					break;
				default:
					return '<';
					break;
			}
			break;
		default:
			return '<';
			break;
	}
}
double caculate(double a,char opnd,double b) {
	//对操作数a,b进行opnd运算,并返回运算结果
	//opnd只能是四则运算符号
	double temp;
	switch(opnd) {
		case '+':
			temp=a+b;
			break;
		case '-':
			temp=a-b;
			break;
		case '*':
			temp=a*b;
			break;
		case '/':
			if(b==0) {
				printf("错误:除数为0.");
				exit(0);
			}
			temp=a/b;
			break;
		default:
			printf("没有此操作符.\n");
			break;
	}
	printf("%f %c %f = %f\n",a,opnd,b,temp);
	return temp;

}
int main() {
	double result=0;
	char *expression=(char*)malloc(sizeof(char)*BUFFERSIZE);
	if(expression==NULL) {
		printf("抱歉系统出错,无法录入您的表达式.\n");
		exit(0);
	}
	printf("请输入你的算术表达式:\n");
	gets(expression);
	Standard(expression);//标准化
	result=procede(expression);
	printf("运算结果为:%f\n",result);
	return 0;
}

今天的文章数据结构栈c语言代码_c++数据结构与算法[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/85379.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注