[cpp]
<p> 有很近沒看了，也望的差不多了。貼上代碼做個記憶吧。</p><p> stack.h</p> #define NULL 0
typedef union
{
double data;
char symbol;
}ElementType;
typedef struct
{
ElementType *pbuffer;
int max;
int top;
}Stack;
Stack *InitStack(int n);
int Push(Stack *sp,ElementType *pdata);
int Pop(Stack *sp,ElementType *pdata);
int DestroyStack(Stack *sp);
int IsEmpty(Stack *sp);
int IsFull(Stack *sp);
int TravereStack(Stack *sp,int (*pfn)(ElementType *pdata));
stack.c
[cpp]
#include "stack.h"
#include <malloc.h>
#include <stdio.h>
#include <string.h>
Stack *InitStack(int n)
{
Stack *sp = NULL;
sp = (Stack *)malloc(sizeof(Stack));
if(!sp)
{
return sp;
}
sp->pbuffer = (ElementType *)malloc(sizeof(ElementType)*n);
if(!sp->pbuffer)
{
free(sp);
sp=NULL;
return sp;
}
sp->max = n;
sp->top = -1;
return sp;
}
int Push(Stack *sp,ElementType *pdata)
{
if(IsFull(sp))
{
return 0;
}
sp->top++;
//sp->pbuffer[sp->top] = *pdata;
memcpy(sp->pbuffer + sp->top,pdata,sizeof(ElementType));
return 1;
}
int Pop(Stack *sp,ElementType *pdata)
{
if(IsEmpty(sp))
{
return 0;
}
*pdata = sp->pbuffer[sp->top];
sp->top--;
return 1;
}
int DestroyStack(Stack *sp)
{
if(sp)
{
free(sp->pbuffer);
free(sp);
return 1;
}
return 0;
}
int IsEmpty(Stack *sp)
{
return sp->top == -1;
}
int IsFull(Stack *sp)
{
return sp->top == sp->max;
}
int TravereStack(Stack *sp,int (*pfn)(ElementType *pdata))
{
int i =0;
for(i=0;i<sp->top+1;i++)
{
pfn(sp->pbuffer+i);
}
printf("\n");
return 1;
}
主要實現的代碼：
[cpp]
#include "stack.h"
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct
{
Stack *spdata;
Stack *spsymbol;
int total;
}Cal;
int SignTab[7][7] = {
// + - * / ( ) #
/* + */ 1, 1, -1, -1, -1, 1, 1,
/* - */ 1, 1, -1, -1, -1, 1, 1,
/* * */ 1, 1, 1, 1, -1, 1, 1,
/* / */ 1, 1, 1, 1, -1, 1, 1,
/* ( */ -1, -1, -1, -1, -1, 0, 2,
/* ) */ 1, 1, 1, 1, 1, 1, 1,
/* # */ -1, -1, -1, -1, -1, 2, 0
};
Cal *InitCal(int n)
{
int i =0;
Cal *cal = (Cal *)malloc(sizeof(Cal));
if(!cal)
{
return cal;
}
cal->total = n;
cal->spdata = InitStack(cal->total);
if(!cal->spdata)
{
free(cal);
return cal;
}
cal->spsymbol = InitStack(cal->total);
if(!cal->spsymbol)
{
free(cal);
return cal;
}
return cal;
}
char * GetStr()
{
int i =0;
char *str = (char *)malloc(sizeof(char)*20);
printf("請輸入計算表達式：");
gets(str);
while(*(str+i))
{
i++;
}
*(str+i) = '#';
*(str+i+1)= '\0';
return str;
}
int IsInt(char *sign)
{
if(*sign>='0' && *sign<='9')
{
return 1;
}
return 0;
}
int Yanzheng(char * str)
{
int i =0;
int j = 0;
int flag = 0;
int zuok = 0;
int youk = 0;
char *sy = "+-*/()#.0123456789";
while(*(str+i))
{
while(*(sy+j))
{
if (*(sy+j) == *(str+i))
{
flag = 1;
break;
}
else
{
flag = 0;
}
j++;
}
j=0;
if (flag)
{
i++;
}
else
{
flag = 0;
return flag;
}
}
i =0;
while(*(str+i))
{
if (*(str+i)=='(')
{
zuok++;
}
if (*(str+i)==')')
{
youk++;
}
for (int m =0; m<4;m++)
{
if (*(str+i)==*(sy+m))
{
if (IsInt(str+i+1) || *(str+i+1)=='#' || *(str+i+1) == '(' || *(str+i+1) == ')')
{
flag = 1;
}
else
{
flag = 0;
return flag;
break;
}
}
}
i++;
}
if (zuok==youk)
{
flag = 1;
}
else
{
flag = 0;
}
return flag;
}
int ShowStack(ElementType *pdata)
{
printf("%f ",*pdata);
return 1;
}
void FreeTwoStack(Cal *cal)
{
if (cal->spdata)
{
free(cal->spdata);
cal->spdata = 0;
}
if (cal->spsymbol)
{
free(cal->spsymbol);
cal->spsymbol = 0;
}
}
int DestroyCal(Cal *cal)
{
if(cal)
{
FreeTwoStack(cal);
free(cal);
return 1;
}
return 0;
}
double SignFun(double *frist,double *last,ElementType *sign)
{
switch(sign->symbol)
{
case '+':
return *frist + *last;
break;
case '-':
return *frist - *last;
break;
case '*':
return (*frist) * (*last);
break;
case '/':
return (*frist) / (*last);
break;
}
return 0;
}
int SignTabR(char signf,char signl)
{
int x = 0;
int y = 0;
int i=0;
char str[] = "+-*/()#";
for(i=0;i<(int)strlen(str);i++)
{
if(signf==*(str+i))
{
x = i;
}
if(signl==*(str+i))
{
y = i;
}
}
return SignTab[x][y];
}
int IsNumber(char * str)
{
return ( (*str >= 0x30 && *str <= 0x39) || (*str == '.') ) ? 1 : 0 ;
}
int ClaExpress(Cal *cal,char *str)
{
int i = 0;
int k = 0;
int s = 0;
char sf;
char sl;
int tabsign;
double data1;
double data2;
double resultfs;
char tmp[50] = {0};
double tmpdata;
ElementType *tmpElem = NULL;//申請的空間太多了。
tmpElem = (ElementType *)malloc(sizeof(ElementType));
ElementType * signf = NULL;
signf = (ElementType *)malloc(sizeof(ElementType));
ElementType * signl = NULL;
signl = (ElementType *)malloc(sizeof(ElementType));
ElementType * cdata1 = NULL;
cdata1 = (ElementType *)malloc(sizeof(ElementType));//必須進行初始化
ElementType * cdata2 = NULL;
cdata2 = (ElementType *)malloc(sizeof(ElementType));//必須進行初始化
while(*(str+i))
{
switch(IsNumber(str+i))
{
case 1:
*(tmp+k) = *(str+i);
k++;
break;
case 0:
if (k!=0)
{
tmpdata = atof(tmp);
tmpElem->data = tmpdata;
Push(cal->spdata,tmpElem);
}
s = 0;
while(*(tmp+s))
{
*(tmp+s) = NULL;
s++;
}
k = 0;
if (k==0)
{
tmpElem->symbol = *(str+i);
Push(cal->spsymbol,tmpElem);
}
break;
}
while(cal->spsymbol->top>0)
{
Pop(cal->spsymbol,signl);
sl = signl->symbol;
Pop(cal->spsymbol,signf);
sf = signf->symbol;
tabsign = SignTabR(sf,sl);
switch(tabsign)
{
case -1 : /* -1 入棧 */
/* 解析的同時已經入棧 */
break ;
case 0 : /* 0 出棧 */
Pop(cal->spsymbol,signf);
Pop(cal->spsymbol,signf);
break ;
case 1 : /* 1 執行 */
Pop(cal->spdata,cdata2);
data2 = cdata2->data;
Pop(cal->spdata,cdata1);
data1 = cdata1->data;
resultfs = SignFun(&data1,&data2,signf);
tmpElem->data = resultfs;
Push(cal->spdata,tmpElem);
tmpElem->symbol = sl;
Push(cal->spsymbol,tmpElem);
break;
case 2 : /* 2 錯誤 */
printf("表達式出錯！");
break ;
default :
break ;
}
}
i++;
}
Pop(cal->spdata,cdata1);
printf("%f",cdata1->data);
return 1;
}
int main()
{
Cal *cal = InitCal(10);
char *str = GetStr();
if (Yanzheng(str))
{
ClaExpress(cal,str);
}
else
{
printf("字符串表達式出錯！");
}
DestroyCal(cal);
return 1;
}
僅僅實現了簡單的功能，做個參考吧。
