#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAXSIZE 100//此程序中存儲(chǔ)單元采用malloc( )函數(shù)分配，但沒(méi)有涉及處理溢出的問(wèn)題，相關(guān)涉及可以參//照realloc( )的使用方法//順序棧的存儲(chǔ)定義typedef struct stack{ ?char *base;//棧底指針?char *top;//棧頂指針?int stacksize;//棧分配的存儲(chǔ)空間大小}SqStack;typedef struct stack2{ ?int *base;//棧底指針?int *top;//棧頂指針?int stacksize;//棧分配的存儲(chǔ)空間大小}SqStack2;SqStack op;//順序棧op用來(lái)存儲(chǔ)運(yùn)算符SqStack2 st;//st用來(lái)存放數(shù)值void Menu(); void InitStack();void trans(char str[],char rpn[]);int value(char rpn[]);int Match(char *p);//*****************************************************************************void Menu(){//界面函數(shù)?printf("*********表達(dá)式求值(只能包含+、-、*、/、（）和正整數(shù))********* ******\n");?printf("請(qǐng)選擇：1.輸入表達(dá)式 2.括號(hào)匹配檢查 3.轉(zhuǎn)換后綴表達(dá)式 4.表達(dá)式計(jì)算5.退出\n");}//*****************************************************************************void InitStack(){//初始化棧op、st?op.base=op.top=(char *)malloc(MAXSIZE*sizeof(char));?if(op.base==NULL) exit(-2);?st.base=st.top=(int *)malloc(MAXSIZE*sizeof(int));?if(st.base==NULL) exit(-2);?op.stacksize=st.stacksize=MAXSIZE;}//*****************************************************************************int Match(char *p){//檢查表達(dá)式中小括號(hào)是否匹配?int flag=0;?SqStack s;?s.base=s.top=(char*)malloc(MAXSIZE*sizeof(char));?if(!s.base) exit(-2);?s.stacksize=MAXSIZE;?while(*p!='\0')?{ if(*p== '(') { ?if(s.top-s.base ==s.stacksize) exit(-1); ? else {*s.top=*p; ? ? ? ? ?s.top++;//將所有的左括號(hào)入棧 ? } } if(*p== ')') { if(s.top!=s.base&&*(s.top-1)=='(') {? ? ? ? ? ?s.top--; ? flag=1; } else flag=2;} p++;?}//while?if((flag==1||flag==0)&&s.top==s.base)??{s.top=s.base;//將棧清空? return 1;}?else if(flag==2) {s.top=s.base;//將棧清空? ? ? ? ? ? ? ? ? ?return 0;}?}//Match //*****************************************************************************void trans(char str[],char rpn[]){//將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式?char ch;?int i=0,t=0;?ch=str[i];?i++;?while(ch!='\0')?{ switch(ch) { case '(': *op.top++=ch; break; ? case ')': while(*(op.top-1)!='(') ? ? ? ? ? ? { rpn[t]=*(op.top-1); ? ? ? ? ? ? ? op.top--; ? ? ? ? ? ? ? t++; ? ? ? ? ? ? } ? ? ? ? ? ? op.top--;//此處必須再次進(jìn)行--運(yùn)算，才能忽略已經(jīng)進(jìn)入的'（'? ? ? ? ? ? ? break; ? case '+': ? case '-': ? ? ? ? ? while(op.top!=op.base && *(op.top-1)!='(') ? ? ? ? ? {rpn[t]=*(op.top-1); ? ? ? ? ? ?op.top--; ? ? ? ? ? ?t++; ? ? ? ? ? } ? ? ? ? ? *op.top++=ch; ? ? ? ? ? break; ? case '*': ? case '/': ? ? ? ? ?while(*(op.top-1)=='*'||*(op.top-1)=='/') ? ? ? ? ?{rpn[t]=*(op.top-1); ? ? ? ? ? op.top--; ? ? ? ? ? t++; ? ? ? ? ?} ? ? ? ? ?*op.top++=ch; ? ? ? ? ?break; ? case ' ':break; ? default: ? ? ? ?while(ch>='0'&&ch<='9') {rpn[t]=ch; t++; ch=str[i]; i++; } i--; rpn[t]='#';t++; ? ? ? ? ? ?}//switch?ch=str[i];?i++;?}//while?while(op.top!=op.base)?{rpn[t]=*(op.top-1);? t++;? op.top--;?}//whilerpn[t]='\0';}//trans//*****************************************************************************int value(char rpn[]){//后綴表達(dá)式求值?int d;?char ch;?int t=0;? ???ch=rpn[t];?t++;?while(ch!='\0')?{ switch(ch) ? {case '+': ? ? ? ? ? ? ? *(st.top-2)=*(st.top-2) + *(st.top-1); ? ? ? ? ? ? ? st.top--; ? ? ? ? ? ? ? break; ? ?case '-': ? ? ? ? ? ? ? ?*(st.top-2)=*(st.top-2) - *(st.top-1); ? ? ? ? ? ? ? st.top--; ? ? ? ? ? ? ? break; ? ?case '*': ? ? ? ? ? ? ? ?*(st.top-2)=*(st.top-2) * *(st.top-1); ? ? ? ? ? ? ? st.top--; ? ? ? ? ? ? ? break; ? ?case '/': ? ? ? ? ? ? ?if(*(st.top-1)!=0) ? ? *(st.top-2)=*(st.top-2) / *(st.top-1); ? ? ? ? ? ? ? else {printf("\n除0錯(cuò)誤！\n"); exit(0); } st.top--; ? ? ? ? ? ? ? break; ? ?default: ? ? ? ?d=0; ? ? ? ?while(ch>='0'&&ch<='9') ? ? ? ? ?{d=10*d+ch-'0'; ? ? ? ? ? ch=rpn[t]; ? ? ? ? ? t++; ? ? ? ? ?} ? ? ? ?*(st.top++)=d; ? ? }//switch ? ch=rpn[t]; t++; ? ? ?? }//whilereturn *(st.top-1);}//value//*****************************************************************************int main(){//主函數(shù)?char str[MAXSIZE],rpn[MAXSIZE],g,f;?//str數(shù)組用來(lái)存儲(chǔ)接收到的字符串，rpn用來(lái)存放轉(zhuǎn)換出來(lái)的后綴表達(dá)式?int i,j=0;?InitStack();?Menu();??while(1){?scanf("%d",&g);?switch(g)?{? ?case 1: printf("請(qǐng)輸入表達(dá)式："); ? ? ? scanf("%s",str); ? i=Match(str);? ? ? ? ? ?break;? ?case 2: if(i==1) printf("匹配成功！\n"); ? ? ? else printf("匹配失??！\n"); ? ? ? break;? ?case 3: if(i==1)? ? {trans(str,rpn); ? ? ? ?printf("后綴表達(dá)式為：%s\n", rpn); ? ?j=1;} ? ? ? else ?{j=0; printf("表達(dá)式中括號(hào)匹配錯(cuò)誤！\n");}? ? break;? ?case 4: if(j) printf("計(jì)算結(jié)果為：%d\n",value(rpn)); ? ? ? else printf("后綴表達(dá)式轉(zhuǎn)換遇到問(wèn)題！\n"); ? ? ? break;? ?case 5: printf("確定要退出系統(tǒng)嗎？(y/n)\n"); ? ? ? getchar();f=getchar(); ? if(f=='y'||f=='Y') exit(0); ? else {printf("請(qǐng)重新選擇！\n");break;}? ?default:printf("輸入錯(cuò)誤！\n"); ? ? ? exit(1);?}//switch?}//while? return 0;}//main