数据结构表达式求值(栈)

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

头文件”cacula.h”

#include <stdio.h>

#include <malloc.h>

#define MAXSIZE 50

typedef struct

{

char data[MAXSIZE];

int top;

}SeqStackc,*PseqStackc;//定义一个线性表栈。

PseqStackc Init_SeqStackc(void)

{

PseqStackc S; S=(PseqStackc)malloc(sizeof(SeqStackc)); if(S) S->top=-1;

return(S);

}//初始化栈。

int Empty_SeqStackc(PseqStackc S)

{

if(S->top==-1)

return(1);

else return (0);

}//判断是否栈空。

int Push_SeqStackc(PseqStackc S,char x)

{

if(S->top==MAXSIZE-1) return (0); else { } S->top++; S->data[S->top]=x; return (1);

}//入栈。

int Pop_SeqStackc(PseqStackc S,char *x)

{

if(Empty_SeqStackc(S)) return (0); else { *x=S->data[S->top]; S->top--; return (1);

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

}

}//出栈。

int GetTop_SeqStackc(PseqStackc S,char *x)

{

if(Empty_SeqStackc(S))

return (0); else

*x=S->data[S->top];

return (1);

}//取栈顶元素。

void Destroy_SeqStackc(PseqStackc *S)

{

if (*S) free(*S); *S=NULL; return ;

}//销毁栈。

typedef struct

{

float data[MAXSIZE]; int top;

}SeqStackf,*PseqStackf;//再定义一个线性表栈。

PseqStackf Init_SeqStackf(void)

{

PseqStackf S; S=(PseqStackf)malloc(sizeof(SeqStackf)); if(S) S->top=-1; return(S);

}//初始化栈。

int Empty_SeqStackf(PseqStackf S)

{

if(S->top==-1) return(1); else return (0);

}//判断是否栈空。

int Push_SeqStackf(PseqStackf S,float x)

{

if(S->top==MAXSIZE-1) return (0); else { S->top++;

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

S->data[S->top]=x;

return (1);

}

}//入栈。

int Pop_SeqStackf(PseqStackf S,float *x)

{

if(Empty_SeqStackf(S)) return (0); else { } *x=S->data[S->top]; S->top--; return (1);

}//出栈。

int GetTop_SeqStackf(PseqStackf S,float *x)

{

if(Empty_SeqStackf(S)) return (0); else *x=S->data[S->top];

return (1);

}//取栈顶元素。

void Destroy_SeqStackf(PseqStackf *S)

{

if (*S) free(*S);

*S=NULL;

return ;

}//销毁栈。

源程序

#include<stdio.h>

#include <iostream.h>

#include<string.h>

#include"cacula.h"

int isnum(char c)

{

} if(c>='0'&&c<='9') return 1; else return 0;

int priority(char op)

{

switch(op)

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

} case '=':return 1; case ')':return 2; case '+': case '-':return 3; case '*': case '%': case '/':return 4; case '(':return 5; default :return 0; }

int infix_exp_value(char *infixexp,char *postfixexp)

{

if(infixexp[strlen(infixexp)-1]!='=') { int z; z=strlen(infixexp); printf("没有以'='结尾！系统自动为你添加'='。\n");

infixexp[z]='=';

infixexp[z+1]='\0';

} PseqStackc S; char c,w,topelement,flag=0; S=Init_SeqStackc(); if(!S) { } printf("初始化失败"); return 0; Push_SeqStackc(S,'#'); w=*infixexp; while((GetTop_SeqStackc(S,&c),c)!='#'||w!='=') { if(w==' ') { infixexp++; w=*infixexp; continue; }//过滤空格字符。 if(w=='.') { *postfixexp=w; postfixexp++;

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

continue; }//小数点'.'字符随前后的数一起放入后辍表达式中。 if(isnum(w)) { } *postfixexp=w; postfixexp++; w=*(++infixexp); if(!isnum(w)&&w!='.') { } *postfixexp=' '; postfixexp++; else { if((GetTop_SeqStackc(S,&c),c)=='('&&w==')') { Pop_SeqStackc(S,&topelement); } w=*(++infixexp); else if((GetTop_SeqStackc(S,&c),c)=='('||priority((GetTop_SeqStackc(S,&c),c))<priority(w)) { } } Push_SeqStackc(S,w); w=*(++infixexp); } else { } Pop_SeqStackc(S,&topelement); *postfixexp=topelement; postfixexp++; *postfixexp='='; *(++postfixexp)='\0'; Destroy_SeqStackc(&S);

return 1;

}//中辍表达式转化成后辍表达式。通过字符型栈来实现。

float postfix_exp(char *A)

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

{

PseqStackf S; float result,a,b,c; char ch; ch=*A++; S=Init_SeqStackf(); while(ch!='=') { if(isnum(ch)) { a=float(ch-'0'); while(*A!=' '&&*A!='.') { ch=*A++; a=a*10+(ch-'0'); }//将数字字符或带小数点的小数点前面的数字字符转化成对应的数赋给a。 if(*A=='.') { A++; b=1.0; while(*A!=' ') { b=b*10; ch=*A++; a=a+(ch-'0')/b; } }//如果小数点后有数字字符，将其转化为对应位置上的小数加在a上。 Push_SeqStackf(S,a);

ch=*A++;

}//保证像"12.5"这样的字符串转化为单精度数12.5，并放入栈中.

else { Pop_SeqStackf(S,&b); Pop_SeqStackf(S,&a); switch(ch) { case '+':c=a+b;break; case '-':c=a-b;break; case '*':c=a*b;break; case '/':if(b!=0) c=a/b; else { printf("Error!出现分母为0情况。\n"); return 0;

这是一个完整的数据结构中,表达式求值的程序,用到栈的知识

} break; case '%':c=(float)((int)a%(int)b);break; } Push_SeqStackf(S,c); } ch=*A++; } GetTop_SeqStackf(S,&result); Destroy_SeqStackf(&S); return (result); }//后辍表达式求表达式的值，通过一个浮点型栈实现的。

void main()

{

printf("******************************************************************************\n");

printf("******************************算 …… 此处隐藏：2563字，全部文档内容请下载后查看。喜欢就下载吧 ……