/***********************************************************************************\
 功    能：    检验含括号的四则运算表达式的合法性  
 输入说明：    按提示输入表达式 ctrl+c 结束输入          

 输出说明：   如果表达式合法则输出 yes ,否则输出 no       
 
测试数据如下：
    
press Ctrl+c to exit !
(((3+4*3+(333+4)+(33*34))/3)+4)
yes
press Ctrl+c to exit !
()
no
press Ctrl+c to exit !
3+4-(3*3)
yes
press Ctrl+c to exit !
8((
no
press Ctrl+c to exit !
8()
no
press Ctrl+c to exit !
3=3
no
press 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;
}

评论