//-------用数组现栈的基本操作的算法实现------------------------ Stack InitStack(int MaxElements)//构造一个空栈 { Stack S; if(MaxElements < MinStackSize) { Puts("Stack size is too small!"); return NULL; } S = (Stack)malloc(sizeof(struct StackRecord)); if(!S) { printf("Out of space!"); return NULL; } S->Array = (ElemType*)malloc(sizeof(ElemType)*MaxElements); if(!S->Array) { printf("Out of space!"); return NULL; } S->StackSize = MaxElements; return MakeEmpty(S); } void DestroyStack(Stack *S);//初始条件：栈S已存在。 操作结果：销毁栈S。 { free(S->Array); free(S); } Stack MakeEmpty(Stack S);//初始条件：栈S非空。 操作结果：将栈S重置为空栈。 { S->TopOfStack = EmptyTop; return S; } int IsEmpty(Stack S);//初始条件：栈S已存在。 操作结果：判断栈是否为空栈。 { return S->TopOfStack == EmptyTop; } int IsFull(Stack S);//初始条件：栈S已存在。 操作结果：判断栈是否为空栈。 { return S->TopOfStack == StackSize-1; } int StackLength(Stack S);//初始条件：栈S已存在。 操作结果：返回栈S结点的个数。 { return S->TopOfStack - EmptyTop; } ElemType GetTop(Stack S);//初始条件：栈S非空。 操作结果：返回栈顶元素的值 { return S->Array[S->TopOfStack]; } //初始条件：栈S已存在。 操作结果：插入元素X为新的栈顶元素 void Push(Stack S, ElemType X); { if(IsFull(S)) Error("Full stack!"); else S->Array[++S->TopOfStack] = X; } void DeleteTop(Stack S);//初始条件：栈S非空。 操作结果：删除S的栈顶元素 { S->TopOfStack--; } ElemType GetTop(Stack S);//初始条件：栈S非空。 操作结果：返回栈顶元素的值 { return S->Array[S->TopOfStack]; } ElemType Pop(Stack S);//初始条件：栈S非空。 操作结果：删除S的栈顶元素, 并返回其值 { ElemType X = GetTop(S); DeleteTop(S); return X; } //--------------------------------------------------------------------------------- /* 举一个简单的例子，利用栈作为临时仓库，存储操作符，将一般表达式转化为逆波兰表达式后， 求逆波兰表达式的值，即得原算术表达式的值，可实现简单四则运算 （为简单起见，设原算术表达式中参加运算的数都只有一个数字）。*/ /*2005-3-10 梁见斌*/ #include <stdio.h> #include<stdlib.h> #include<string.h> #define MAX 30 int GetStr(char str[]);/*输入算术表达式*/ void Print(char exp[], int len);/*输出表达式*/ int Change(char str[], char exp[]);/*将一般表达式转化为逆波兰表达式*/ float JiSuan(char exp[]); /*求逆波兰表达式的值*/ int main(void) { char str[MAX], *pstr=str;/*存储原算术表达式*/ char exp[MAX], *pexp=exp;/*存储转化成的逆波兰表达式*/ float result; /*存储逆波兰表达式的值*/ int len1, len2;/*len1存储原算术表达式的长度，len2存储转化成的逆波兰表达式的长度*/ len1=GetStr(pstr); printf("原算术表达式: "); Print(pstr, len1); len2=Change(pstr, pexp); printf("逆波兰表达式: "); Print(pexp,len2); result=JiSuan(pexp); printf("The result is: %f", result); system("pause"); return 0; } int GetStr(char str[]) { int i=0; printf("请输入算术表达式: "); do{ scanf("%c", &str[i++]);/*设字符‘#’为表达式的终止符*/ }while(str[i-1] != '#' && i < MAX); return i; } void Print(char exp[], int len) { int i; for(i=0; i<len; i++) printf("%c", exp[i]); printf("\n"); } int Change(char str[], char exp[]) { int i, t, top;/*t作为exp的下标，top作为stack的下标，i作为str的下标*/ char stack[MAX], ch;/*作为栈使用*/ t=0; i=0; top=0; stack[0]='#'; ch=str[i++]; while(ch != '#') { if(ch >= '0' && ch <= '9') //如果是数字，直接存入数组 exp[t++]=ch; else if(ch == '(') //如果是左括号，入栈 stack[++top]=ch; else if(ch == ')')//如果是右括号，出栈 { while(stack[top] != '(') exp[t++]=stack[top--]; top--; } else if(ch == '+' || ch == '-') //如果是操作数，根据优先级出，入栈 { while(top != 0 && stack[top] != '(') exp[t++]=stack[top--]; stack[++top]=ch; } else if(ch == '*' || ch == '/') { while(stack[top] == '*' || stack[top] == '/') exp[t++]=stack[top--]; stack[++top]=ch; } else //不理会错误字符 printf("\n%c ia a wrong letter\n", ch); ch=str[i++]; } while(top != 0) exp[t++]=stack[top--]; exp[t]='#'; return t+1; } float JiSuan(char exp[]) { float stack[MAX], d;/*作为栈使用*/ char c; int i=0, t=0, top=0; c=exp[t++]; while(c != '#') { d=c-'0'; if(c >= '0' && c <= '9') stack[top++]=d; else { switch(c) { case '+': stack[top-2]=stack[top-2]+stack[top-1]; break; case '-': stack[top-2]=stack[top-2]-stack[top-1]; break; case '*': stack[top-2]=stack[top-2]*stack[top-1]; break; case '/': if(stack[top] != 0) stack[top-2]=stack[top-2]/stack[top-1]; else printf("It's error!\n"); break; } top--; } c=exp[t++]; } return stack[top-1]; }
评论