栈实现表达式计算(完整)

1、 /ExpressionSeqStack.c#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#define ERR_NOMEMORY -1 /内存分配错误#define ERR_INVALIDPARAM -2 /输入参数无效#define ERR_OVERFLOW -3 /溢出#define ERR_ILLEGALINDEX -4 /非法的索引位置#define ERR_EMPTYRESULT -5 /无返回结果#define STACK_MAXSIZE

2、 100 /顺序栈存放的最大元素个数typedef int datatype; /顺序栈元素的类型 typedef struct /顺序栈结构类型datatype* base;datatype* top;int size;SeqStack;/*初始化顺序栈*/int InitStack(SeqStack *stack)if(!stack)return ERR_INVALIDPARAM; /顺序栈无效/分配内存空间stack->base=(datatype*)malloc(STACK_MAXSIZE*sizeof(datatype);if(!stack->base)return ER

3、R_NOMEMORY; /内存分配失败 stack->top=stack->base; /初始栈顶位置 stack->size=STACK_MAXSIZE; /顺序栈的大小为STACK_MAXSIZE return 0;/*栈是否为空*/int StackEmpty(SeqStack *stack)if(!stack)return ERR_INVALIDPARAM; /顺序栈无效 return(stack->top=stack->base); /True为空；False为非空/*清空栈*/int ClearStack(SeqStack *stack)if(!sta

4、ck)return ERR_INVALIDPARAM; /顺序栈无效stack->top=stack->base; /重置栈顶位置return 0;/*取得栈顶元素*/int GetTop(SeqStack *stack,datatype *e) if(!stack)return ERR_INVALIDPARAM; /顺序栈无效 if(stack->top=stack->base)return ERR_EMPTYRESULT;/栈为空 *e=*(stack->top-1); /返回栈顶元素 return 0;/*将元素入栈*/int Push(SeqStack*s

5、tack,datatype e)if(!stack)return ERR_INVALIDPARAM; /顺序栈无效if(stack->top>stack->base+stack->size-1)return ERR_OVERFLOW; /(1)栈满*(stack->top)=e; /(2)将元素e赋予新的栈顶位置stack->top+; /(3)栈顶指针增1return 0;/*将元素出栈*/int Pop(SeqStack *stack,datatype *e)if(!stack)return ERR_INVALIDPARAM; /顺序栈无效if(stac

6、k->top=stack->base)return ERR_EMPTYRESULT; /(1)栈为空stack->top-; /(2)栈顶指针减1*e=*(stack->top); /(3)返回栈顶元素return 0;/*比较两运算符的优先关系*/int ComparePriority(char op1,char op2)int priority1=0,priority2=0;if(op1='+'|op1='-')priority1=1; /运算符1的优先级else if(op1='*'|op1='/')

7、priority1=2;if(op2='+'|op2='-')priority2=1; /运算符2的优先级else if(op2='*'|op2='/')priority2=2;return(priority1-priority2); /op1>op2,op1=op2,op1<op2/*中缀表达式转换为后缀表达式*/int InfixToSuffix(char *infix,char *suffix)char c;int t=0;char *pInfix=infix; /中缀表达式char *pSuffix=suffi

8、x; /后缀表达式/初始化顺序栈SeqStack optr;InitStack(&optr);/依次扫描中缀表达式while(*pInfix!='0')c=*pInfix; /(1)读取中缀表达式的每个字符if(c>='0'&&c<='9') /(2)该字符为操作数*pSuffix=c; /直接添加到后缀表达式中pSuffix+; /指向保存下一个字符的位置else if(c='(') /(3)当前字符为左括号"("Push(&optr,c); /直接将其添加到栈中e

9、lse if(c=')') /(4)当前字符为右括号")"Peek(&optr,&t); /取得括号内的运算符while(t!='(')*pSuffix=t; /将括号内的所有操作数和运 pSuffix+; /算符添加到后缀表达式中Pop(&optr,&t); /移除已添加的运算符Peek(&optr,&t); /查找下一个运算符Pop(&optr,&t); /将左括号移除else if(StackEmpty(&optr) /(5)运算符为空时直接将其入栈Push(&am

10、p;optr,&t);else /将栈中的所有运算符添加到后缀表达式中Peek(&optr,&t); /取栈顶运算符，当前运算符的优先级高于if(ComparePriority(c,t)>0) /栈顶运算符的优先级将直接入栈Push(&optr,&t);else /否则，将栈中所有优先级高于当前优先级 /的运算符添加到后缀表达式中while(!StackEmpty(&optr)&&ComparePriority(c,t)<=0)*pSuffix=t;pSuffix+;Pop(&optr,&t); /移除

11、已添加到后缀表达式中的运算符Peek(&optr,&t); /查找下一个运算符Push(&optr,c); /将当前运算符添加到栈中/扫描中缀表达式的下一个字符pSuffix+;/(6)将剩余的运算符添加到后缀表达式中while(!StackEmpty(&optr)Pop(&optr,&t);*pSuffix=t;pSuffix+;/释放顺序栈的内存free(optr.base);return0;/*计算两个操作数的值*/int Operate(int a,char op,int b)Switch(op)case'+':retur

12、na+b; /加法运算case'-':returna-b; /减法运算case'*':returna*b; /乘法运算case'/':returna/(b=0?1:b); /除法运算return 0;/*计算后缀表达式的值*/int CalculateExpressionBySuffix(char *suffix)char c;int a=0,b=0,s=0;const char *pSuffix=suffix; /后缀表达式/初始化程序栈SeqStack opnd;InitStack(&opnd);/从左到右依扫描后缀表达式while(

13、*pSuffix !='0') c=*pSuffix; /读取后缀表达式的每个字符if(c>='0'&&c<='9') /该字符为操作数Push(&opnd,c-48); /直接将其添加到栈中else /该字符为运算符Pop(&opnd,&b); /弹出两个操作数Pop(&opnd,&a);s=Operate(a,c,b); /将则两个操作数根据运算符进行计算Push(&opnd, s); /将计算结果重新压入栈中pSuffix+; /查找下一个操作数Pop(&opnd,&s); /弹出最终的计算结果free(opnd.base); /释放顺序表内存return s;/*程序主函数*/int main()char infix80=0;/保存中缀表达式char suffix80=0;/保存后缀表达式 int result=0; /表达式的计算结果 printf("请输入算术表达式："