#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAXSIZE 100//此程序中存储单元采用malloc( )函数分配，但没有涉及处理溢出的问题，相关涉及可以参//照realloc( )的使用方法//顺序栈的存储定义typedef struct stack{ char *base;//栈底指针 char *top;//栈顶指针 int stacksize;//栈分配的存储空间大小}SqStack;typedef struct stack2{ int *base;//栈底指针 int *top;//栈顶指针 int stacksize;//栈分配的存储空间大小}SqStack2;SqStack op;//顺序栈op用来存储运算符SqStack2 st;//st用来存放数值void Menu(); void InitStack();void trans(char str[],char rpn[]);int value(char rpn[]);int Match(char *p);//*****************************************************************************void Menu(){//界面函数 printf("*********表达式求值(只能包含+、-、*、/、（）和正整数)********* ******\n"); printf("请选择：1.输入表达式 2.括号匹配检查 3.转换后缀表达式 4.表达式计算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){//检查表达式中小括号是否匹配 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++;//将所有的左括号入栈 } } 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[]){//将中缀表达式转换为后缀表达式 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--;//此处必须再次进行--运算，才能忽略已经进入的'（' 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[]){//后缀表达式求值 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错误！\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(){//主函数 char str[MAXSIZE],rpn[MAXSIZE],g,f; //str数组用来存储接收到的字符串，rpn用来存放转换出来的后缀表达式 int i,j=0; InitStack(); Menu(); while(1){ scanf("%d",&g); switch(g) { case 1: printf("请输入表达式："); 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("后缀表达式为：%s\n", rpn); j=1;} else {j=0; printf("表达式中括号匹配错误！\n");} break; case 4: if(j) printf("计算结果为：%d\n",value(rpn)); else printf("后缀表达式转换遇到问题！\n"); break; case 5: printf("确定要退出系统吗？(y/n)\n"); getchar();f=getchar(); if(f=='y'||f=='Y') exit(0); else {printf("请重新选择！\n");break;} default:printf("输入错误！\n"); exit(1); }//switch }//while return 0;}//main
- 1 回答
- 0 关注
- 1341 浏览
添加回答
举报
0/150
提交
取消