棧實(shí)現(xiàn)表達(dá)式計(jì)算(完整)

1、 /ExpressionSeqStack.c#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#define ERR_NOMEMORY -1 /內(nèi)存分配錯誤#define ERR_INVALIDPARAM -2 /輸入?yún)?shù)無效#define ERR_OVERFLOW -3 /溢出#define ERR_ILLEGALINDEX -4 /非法的索引位置#define ERR_EMPTYRESULT -5 /無返回結(jié)果#define STACK_MAXSIZE

2、 100 /順序棧存放的最大元素個數(shù)typedef int datatype; /順序棧元素的類型 typedef struct /順序棧結(jié)構(gòu)類型datatype* base;datatype* top;int size;SeqStack;/*初始化順序棧*/int InitStack(SeqStack *stack)if(!stack)return ERR_INVALIDPARAM; /順序棧無效/分配內(nèi)存空間stack->base=(datatype*)malloc(STACK_MAXSIZE*sizeof(datatype);if(!stack->base)return ER

3、R_NOMEMORY; /內(nèi)存分配失敗 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;/*比較兩運(yùn)算符的優(yōu)先關(guān)系*/int ComparePriority(char op1,char op2)int priority1=0,priority2=0;if(op1='+'|op1='-')priority1=1; /運(yùn)算符1的優(yōu)先級else if(op1='*'|op1='/')

7、priority1=2;if(op2='+'|op2='-')priority2=1; /運(yùn)算符2的優(yōu)先級else if(op2='*'|op2='/')priority2=2;return(priority1-priority2); /op1>op2,op1=op2,op1<op2/*中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式*/int InfixToSuffix(char *infix,char *suffix)char c;int t=0;char *pInfix=infix; /中綴表達(dá)式char *pSuffix=suffi

8、x; /后綴表達(dá)式/初始化順序棧SeqStack optr;InitStack(&optr);/依次掃描中綴表達(dá)式while(*pInfix!='0')c=*pInfix; /(1)讀取中綴表達(dá)式的每個字符if(c>='0'&&c<='9') /(2)該字符為操作數(shù)*pSuffix=c; /直接添加到后綴表達(dá)式中pSuffix+; /指向保存下一個字符的位置else if(c='(') /(3)當(dāng)前字符為左括號"("Push(&optr,c); /直接將其添加到棧中e

9、lse if(c=')') /(4)當(dāng)前字符為右括號")"Peek(&optr,&t); /取得括號內(nèi)的運(yùn)算符while(t!='(')*pSuffix=t; /將括號內(nèi)的所有操作數(shù)和運(yùn) pSuffix+; /算符添加到后綴表達(dá)式中Pop(&optr,&t); /移除已添加的運(yùn)算符Peek(&optr,&t); /查找下一個運(yùn)算符Pop(&optr,&t); /將左括號移除else if(StackEmpty(&optr) /(5)運(yùn)算符為空時直接將其入棧Push(&am

10、p;optr,&t);else /將棧中的所有運(yùn)算符添加到后綴表達(dá)式中Peek(&optr,&t); /取棧頂運(yùn)算符，當(dāng)前運(yùn)算符的優(yōu)先級高于if(ComparePriority(c,t)>0) /棧頂運(yùn)算符的優(yōu)先級將直接入棧Push(&optr,&t);else /否則，將棧中所有優(yōu)先級高于當(dāng)前優(yōu)先級 /的運(yùn)算符添加到后綴表達(dá)式中while(!StackEmpty(&optr)&&ComparePriority(c,t)<=0)*pSuffix=t;pSuffix+;Pop(&optr,&t); /移除

11、已添加到后綴表達(dá)式中的運(yùn)算符Peek(&optr,&t); /查找下一個運(yùn)算符Push(&optr,c); /將當(dāng)前運(yùn)算符添加到棧中/掃描中綴表達(dá)式的下一個字符pSuffix+;/(6)將剩余的運(yùn)算符添加到后綴表達(dá)式中while(!StackEmpty(&optr)Pop(&optr,&t);*pSuffix=t;pSuffix+;/釋放順序棧的內(nèi)存free(optr.base);return0;/*計(jì)算兩個操作數(shù)的值*/int Operate(int a,char op,int b)Switch(op)case'+':retur

12、na+b; /加法運(yùn)算case'-':returna-b; /減法運(yùn)算case'*':returna*b; /乘法運(yùn)算case'/':returna/(b=0?1:b); /除法運(yùn)算return 0;/*計(jì)算后綴表達(dá)式的值*/int CalculateExpressionBySuffix(char *suffix)char c;int a=0,b=0,s=0;const char *pSuffix=suffix; /后綴表達(dá)式/初始化程序棧SeqStack opnd;InitStack(&opnd);/從左到右依掃描后綴表達(dá)式while(

13、*pSuffix !='0') c=*pSuffix; /讀取后綴表達(dá)式的每個字符if(c>='0'&&c<='9') /該字符為操作數(shù)Push(&opnd,c-48); /直接將其添加到棧中else /該字符為運(yùn)算符Pop(&opnd,&b); /彈出兩個操作數(shù)Pop(&opnd,&a);s=Operate(a,c,b); /將則兩個操作數(shù)根據(jù)運(yùn)算符進(jìn)行計(jì)算Push(&opnd, s); /將計(jì)算結(jié)果重新壓入棧中pSuffix+; /查找下一個操作數(shù)Pop(&opnd,&s); /彈出最終的計(jì)算結(jié)果free(opnd.base); /釋放順序表內(nèi)存return s;/*程序主函數(shù)*/int main()char infix80=0;/保存中綴表達(dá)式char suffix80=0;/保存后綴表達(dá)式 int result=0; /表達(dá)式的計(jì)算結(jié)果 printf("請輸入算術(shù)表達(dá)式："