/***********************************************************************************\ 功 能： 检验含括号的四则运算表达式的合法性 输入说明： 按提示输入表达式 ctrl+c 结束输入 输出说明： 如果表达式合法则输出 yes ,否则输出 no 测试数据如下： press Ctrl+c to exit !(((3+4*3+(333+4)+(33*34))/3)+4)yespress Ctrl+c to exit !()nopress Ctrl+c to exit !3+4-(3*3)yespress Ctrl+c to exit !8((nopress Ctrl+c to exit !8()nopress Ctrl+c to exit !3=3nopress Ctrl+c to exit ! 算法说明： 象拨竹笋一样从最内层括号开始，注意将括号改为数字不改变表达式的合法性 寻找最内层括号：找表达式最左的')' ，找表达式最右并且在前面所找')'左边 的'('这对括号就是最内层括号，检验这两个位置的前后是否合法，例如对 '(' 之前不能有数字，之后不能有运算符，检验完后将它们改为数字。 处理完括号就处理运算符，方法和括号的差不多。 语 言： 非标准 C 编译环境： VC ++ 6.0 Author ： 江南孤峰 Time ：2006--11--29 独学而无友，则孤陋而寡闻 编程爱好者群 : 28011342 \************************************************************************************/ #include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#include <ctype.h> #define MAX 100 char* GetFirst(char *p){ /* 找表达式 p 中的运算符 ,返回找到的位置 */ char *f; if((f = strchr(p,'+'))) return f; if((f = strchr(p,'-'))) return f; if((f = strchr(p,'*'))) return f; if((f = strchr(p,'/'))) return f; return NULL;} int Deny(char *pstr,int len){ /* 测试表达式的合法性，是则返回 1，否则返回 0 */ int i = 0; char *stack[MAX],*p,*a,*b,*c; if(strchr("+-*/)",*pstr)) return 0; /* 首位置的合法性检验 */ p = (char*)malloc(len); strcpy(p,pstr); /* 避免改变原表达式 */ for(i = 0; i < len; i ++){ /* 表达式字符合法性检查 */ if(!isdigit(*(p+i)) && !strchr("+-*/()",*(p+i))) return 0; } while(1){ /* 括号处理 */ a = strchr(p,')'); if(!a && strchr(p,'(')) return 0; for(i = 0,c = b = strrchr(p,'('); b && b > a;i ++){ stack[i] = c; *c = '1'; c = b = strrchr(p,'('); } if(!a && !b) break; for(i --;i >= 0; i --) *stack[i] = '('; if((!a && b) || (a && !b)) return 0; else{ /* 括号左右字符合法性检验 */ if(!isdigit(*(a-1)) || !isdigit(*(b+1))) return 0; if(a != (p+len-1)){ if(!(strchr("+-*/)",*(a+1)))) return 0; } if(b != p){ if(!strchr("+-*/(",*(b-1))) return 0; } /* 将括号改为数字 */ *a = '1'; *b = '1'; } } while(1){/* 运算符左右字符合法性检验 */ if(!(a = GetFirst(p))) break; if(!(isdigit(*(a-1)))) return 0; if(!(isdigit(*(a+1)))) return 0; *a = '1'; } return 1;} int main(){ char array[100]; while(1){ puts("press Ctrl+c to exit !"); gets(array); if(Deny(array,strlen(array))) printf("yes\n"); else printf("no\n"); } return 0;}
评论