表达式判断 帅呆了的标题
表达式判断帅呆了的题目Problem D: 表达式 /* 设S是一个合法的表达式，E为一个数字字符序列，则合法的表达式
表达式判断 帅呆了的题目
Problem D: 表达式 /* 设S是一个合法的表达式，E为一个数字字符序列，则合法的表达式可以表示为：E, +E, -E, (S)，+(S)，-(S)，S+(S)，S-(S)，S*(S)，S/(S) 等。 (E可以是全‘0’的字符串)。请注意+S, -S, S+S等不一定是合法的表达式，因为可能出现如“+-E”运算符相邻情况，另外出现“()”括号中没有元素的表达式也是不合法的。*/#include<stdio.h>#include<string.h>#include<stdlib.h>#define ORI 0#define NUM 1#define CAL 2#define BCK 3#define FAIL -1int f[4][1 << 7];char buf[1 << 10];void init(){ int i; memset(f, FAIL, sizeof(f)); //二维数组也是可以这样初始化的 //下面的几句代码使得只有输入的是运算符加减乘除 或者数字的时候才能不等于FATL 其它时候全部是FATL 即-1 f[ORI]['+'] = f[ORI]['-'] = f[ORI]['*'] = f[ORI]['/'] = CAL;//我们关心的不是加减乘除 所以忽略主要矛盾 形象化符号 f[NUM]['+'] = f[NUM]['-'] = f[NUM]['*'] = f[NUM]['/'] = CAL; for(i = '0'; i <= '9'; ++ i) //数字也是按字符输入的 所以要用 其对应的ASCII值 f[ORI][i] = f[NUM][i] = f[CAL][i] = NUM;//把输入的数字 全部变成num=1 f[ORI]['('] = f[CAL]['('] = BCK;}void Delete_Blank() ///{ // int i, j; // for(i = j = 0; buf[i]; ++ i) // if(buf[i] != ' ' && buf[i] != '\t') // buf[j ++] = buf[i]; //这个地方帅啊 用一个数组就解决了 预处理 哈哈 buf[j] = 0; //} //int Find_Bck(int start){ int i, cnt = 1; for(i = start + 1; buf[i]; ++ i)//下面很帅 通过加加 减减 判断（ ）的平衡 { if(buf[i] == '(') ++ cnt; else if(buf[i] == ')') -- cnt; if(!cnt) return i;/*这里牛逼啊 已经知道第一个是（ 所以初始cnt=1 之后如果遇见） 马上cnt=0了 马上返回）的地址 对（）内的内容进行检查是否有不是正确符号的符号 。 如果 在）之前又发现好多（ 则一直加加 直到对称了以后 返回最后一个）地址 然后回溯 DFA 即 再次调用DFA 把括号中的括号内的内容检查一遍 */ } return 0;//如果（ ） 不对称 则直接返回0}bool DFA(int l, int r){ int state = ORI, i, nex; for(i = l; i < r; ++ i) { state = f[state][buf[i]]; /*若第一个数是数字 则state此时为1 f[state] 则下次则不是f[0][]而是f[1][] 若第一个不是数字 而是-或+ 则state的值变成了2 如果再下一个字符是加减乘除的话而对应的f[2][]中的内容是-1 即FAIL 避免了2个运算符号同时出现的可能 */ if(state == BCK) { nex = Find_Bck(i);//这时候 已经找到了（ 并得到了（的地址给了nex if(!nex || !DFA(i + 1, nex)) return false;//如果nex不为0 或者 继续调用（）内内容发现新的错误 则返回错误表达式 state = NUM;// i = nex; } else if(state == FAIL)//同时出现了两个运算符号 return false; } return state == NUM;//如果没有扩号 最后一个 一定是数字 才对 所以判断是否 等于NUM 如果有括号我们直接把state赋值成num就行了}int main(){ init(); while(gets(buf)) //while gets 就行 不用非要等于 NULL { Delete_Blank(); if(!buf[0]) {puts("");continue;} //空行就是长度为0的字符串 printf(DFA(0, strlen(buf)) ? "Yes\n" : "No\n"); } return 0;}
