《逆波兰式(中缀转后缀).docx》由会员分享，可在线阅读，更多相关《逆波兰式(中缀转后缀).docx（6页珍藏版）》请在金锄头文库上搜索。
1、逆波兰式(中缀转后缀)-逆波兰式-#include#include#include#include#include #includeStatus YunSuanFu(SElemType e);char Precede(int x,int y);Status In(SElemType e);Status HouZhui(LinkList Exp_b);/中缀转后缀Status Result(LinkList Exp_b,SElemType *e);Status JiSuan(SElemType a,SElemType b,SElemType ch);void main()LinkList Exp
2、_b;SElemType e;InitList(&Exp_b);HouZhui(Exp_b);/把表达式进行进行入栈printf(后缀表达式为：);printList(Exp_b);Result(Exp_b, &e);/求结果printf(结果为： %dn,e);/判断是否为元算字符Status In(SElemType e)switch (e)case +: case -:case *:case /:case (:case ):case #:return 1;default: return 0;/把字符串转换为相对应的字符串数组序号Status YunSuanFu(SElemType e)
3、switch(e)case +: return 0;case -:return 1;case *:return 2;case /:return 3;case (:return 4;case ):return 5;case #:return 6;/比较级char Precede(int x, int y) char Prior77 = , , , , , , ,6|y6)return FALSE;else return Priorxy;/中缀转后缀,并存入Exp_b表中Status HouZhui(LinkList Exp_b)SqStack OPTR;SElemType Exp_a,e;/读入
4、字符变量int x,y,n=1;InitStack(&OPTR);printf(请输入表达式：n);Exp_a = getchar();Push(&OPTR, #);while( Exp_a != #|e != #)if(In(Exp_a) /判断是否为算数表达式x=YunSuanFu(e);y=YunSuanFu(Exp_a);switch (Precede(x,y) /把数组中的字符提出case :Pop(&OPTR, &e);/运算符栈的栈顶符算出栈InsertList(Exp_b,n,e);n+; else if(Exp_a= 0&Exp_anext;SqStack OPND;Init
5、Stack(&OPND);/运算数栈while(p != NULL)if(!In(p-data)Push(&OPND,(int)(p-data)-48);elsePop(&OPND, &b);/运算数栈的栈顶数算出栈Pop(&OPND, &a);/运算数栈的栈顶数算出栈Push(&OPND,JiSuan(a,b,p-data);p = p-next; Pop(&OPND, &a);/把运算数中的栈最后的结果数字提出*e = a;-LB-#include#include#include#define ERROR 0#define OK 1#define EQUAL 1#define OVERFL
6、OW -1typedef int Status;typedef char SElemType;struct LNODESElemType data;struct LNODE * next;typedef struct LNODE LNode;typedef struct LNODE * LinkList;/线性结构的链式存储结构的定义int InitList(LinkList *L);/带头结点单项链表L的初始化int InsertList(LinkList L,int i,SElemType e);/在链表L的第i个元素前插入新元素eint printList(LinkList L);/输出
7、链表Lint LengthList(LinkList L);/求链表长度int InitList(LinkList *L)* L = (LNode *)malloc(sizeof(LNode);if(!L)exit(ERROR);(*L)-next = NULL;return OK;int InsertList(LinkList L,int i,SElemType e)LinkList p,s;int j;p=L;j=0;while (p&jnext;+j;if(!p|ji-1)return ERROR;s = (LinkList)malloc(sizeof(LNode);s-data = e
8、;s-next = p-next;p-next = s;return OK;int printList(LinkList L)LinkList p;p = L;while(p-next)p = p-next;printf(%c ,p-data);printf(n);return OK;int LengthList(LinkList L)int j=0;while(L-next)L=L-next;j+;return j;int GetList(LinkList L,int m)int n;int j;int i;LinkList p,q,s;p = L;q = L;s = L;j = 1;i =
9、 1;n = 0;/第一种，链表中含有与m相同的数while (p-next)if (p-next-data=m)return j;+j;p = p-next;/第二种，链表中没有与m相同的元素，但m在链表数的自然递减范围内while (q-next-data m & q-next != NULL)if (q-next-next = NULL)return LengthList(L);if (q-next-next-data next;/最后一种m大于头结点数，返回0；if (s-next-data #include#include#define TRUE 1#define FALSE 0#d
10、efine OK 1#define ERROR 0#define OVERFLOW 0#define INFEASIBLE -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SElemType; /栈中元素为int型typedef struct /栈的顺序存储表示SElemType * base; /栈构造之前和销毁之后，值为NULLSElemType * top; /栈顶指针int stacksize; /当前已分配存储空间SqStack;Status InitStack
11、(SqStack * S);/构造一个空栈Status DestoryStack(SqStack *S);/销毁栈SStatus StackEmpty(SqStack S); /若S为空栈，则返回TURE，后则返回FALSEStatus GetTop(SqStack S,SElemType *e); /若栈不为空，则用e返回S的栈顶元素，并返回OK，否则返回ERRORStatus Push(SqStack *S,SElemType e); /插入元素e为新的栈顶元素Status Pop(SqStack *S,SElemType *e); /若栈不为空，则删除S的栈顶元素，用e返回其值，并返回O
12、K否则ERRORStatus StackTraverse(SqStack S); /遍历栈，输出每个数据元素/创建一个空栈SStatus InitStack(SqStack *S)S-base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(S-base)exit(OVERFLOW);S-top = S-base;S-stacksize = STACK_INIT_SIZE;return OK;/销毁栈SStatus DestoryStack(SqStack *S) /销毁栈Sif(S-base)free(S-base);
13、S-top = S-base = NULL;return OK;/鉴定空栈Status StackEmpty(SqStack S)if(S.top = S.base)return TRUE;elsereturn FALSE;/栈不为空，返回栈S的栈顶元素Status GetTop(SqStack S,SElemType * e)if(S.top = S.base)return ERROR;*e = *(S.top-1);return OK;/插入元素e为新的栈顶元素Status Push(SqStack *S,SElemType e)/判断栈满if(S-top-S-base = S-stack
14、size)S-base = (SElemType *) realloc (S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S-base)exit(OVERFLOW);S-top = S-base + S-stacksize;S-stacksize += STACKINCREMENT;*S-top + = e;return OK;/栈不为空，删除栈顶Status Pop(SqStack *S,SElemType *e)if(S-top = S-base)return ERROR;*e = * (-S-top);return OK;/遍历Status StackTraverse(SqStack S)SElemType *p = S.base;int i = 0;if(S.base = S.top)printf(堆栈已空!n);return OK;while(pS.top)printf(%c,*p+);printf(n);return OK;
