Problem D: 表达式
Time Limit: 1 Sec
Memory Limit:
4 MB
SUBMIT: 375
Solved: 31
[SUBMIT][STATUS]
Description
设S是一个合法的表达式,E为一个数字字符序列,则合法的表达式可以表示为:E, +E, -E, (S),+(S),-(S),S+(S),S-(S),S*(S),S/(S) 等。(E可以是全‘0’的字符串)。
请注意+S, -S, S+S等不一定是合法的表达式,因为可能出现如“+-E”运算符相邻情况,另外出现“()”括号中没有元素的表达式也是不合法的。
Input
每行一个字符串,最长不超过1023个字符。可能有空行。
Output
如果表达式合法,输入“Yes”,否则输入“No”,然后换行。
如果表达式为空,则输出一个空行。
Sample Input
Sample Output
/*
这道题,纠错时间主要在两个栈的存储顺序不一样!
*/
#include <cstdio>
#include <cstring>
bool isOpe(char c)
{
if(c=='+' || c=='-' || c=='*' || c=='/')
return true;
return false;
}
bool isDig(char c)
{
if(c>='0' && c<='9')
return true;
return false;
}
bool check(char stack[],int top)
{
bool ok=true;
for(int i=0;i<=top;i++)
{
if(isOpe(stack[i]) && (i==top || (i<top && isOpe(stack[i+1]))))
ok=false;
else if(isDig(stack[i]) && i<top && stack[i+1]=='#')
ok=false;
else if(stack[i]=='#' && i<top && isOpe(stack[i+1]))
ok=false;
}
return ok;
}
int main()
{
freopen("data.in","r",stdin);
const int nMax=1024+10;
char stack1[nMax],stack2[nMax];
char line[nMax];
int top1,top2;
while(gets(line))
{
bool ok=true;
top1=-1;
top2=-1;
int len=strlen(line);
if(len==0)
{
printf("\n");
continue;
}
for(int i=0;i<len;i++)
{
if(line[i]!=')')
stack1[++top1]=line[i];
else
{
while(top1!=-1 && stack1[top1]!='(')
stack2[++top2]=stack1[top1--];
for(int j=0;j<=top2/2;j++)
{
char temp=stack2[top2-j];
stack2[top2-j]=stack2[j];
stack2[j]=temp;
}
if(top2==-1) ok=false;
else if(top1==-1) ok=false;
else if(!check(stack2,top2)) ok=false;
else if(stack1[top1--]!='(') ok=false;
else top2=-1,stack1[++top1]='#';
}
}
if(!check(stack1,top1)) ok=false;
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
/*
解法借鉴与:CSGrandeur
主要思想:
①去空格
②括号匹配,递归判断处理
③确定性有限自动生成器---*****
*/
#include <cstdio>
#include <cstring>
const int nMax=1024+10;
char line[nMax];
int f[4][1<<7];
#define ORI 0
#define NUM 1
#define OPR 2
#define YKH 3
#define FAIL -1
void Delete_Blank(int len)
{
int i,j;
for(i=0,j=0;i<len;i++)
{
if(line[i]!=' ' && line[i]!='\t')
line[j++]=line[i];
}
line[j]=0;
}
void Init()
{
memset(f,-1,sizeof(f));
f[ORI]['+']=f[ORI]['-']=OPR;
f[NUM]['+']=f[NUM]['-']=f[NUM]['*']=f[NUM]['/']=OPR;
for(int i='0';i<='9';i++)
f[ORI][i]=f[NUM][i]=f[OPR][i]=NUM;
f[ORI]['(']=f[OPR]['(']=YKH;
}
int Find_Next_Pos(int x,int y)
{
int num=1;
for(int i=x;i<y;i++)
{
if(line[i]=='(')
num++;
else if(line[i]==')')
num--;
if(num==0)
return i;
}
return -1;
}
bool IsExpression(int x,int y)
{
int state=ORI;
for(int i=x;i<y;i++)
{
state=f[state][line[i]];
if(state==YKH)
{
int next=Find_Next_Pos(i+1,y);
if(next!=-1 && IsExpression(i+1,next))
state=NUM,i=next;
else return false;
}
else if(state==FAIL)
return false;
}
return state==NUM;
}
int main()
{
freopen("data.in","r",stdin);
while(gets(line))
{
if(!line[0])
{
printf("\n");
continue;
}
int len=strlen(line);
Delete_Blank(len);
len=strlen(line);
Init();
if(IsExpression(0,len))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
分享到:
相关推荐
将中缀表达式,转换为后缀表达式。 并由中缀表达式及后缀表达式生成二叉树,用于判断表达式是否合法。(包括表达式的逻辑判断)
逆波兰式的生成(包括输入表达式是否合法的判定)
主要介绍了详解Javascript判断Crontab表达式是否合法的相关资料,需要的朋友可以参考下
JavaScript正则表达式验证身份证号码是否合法(两种方法)分析.docx
Java正则表达式的使用,判断html、电话等是否符合规定、、、
//可以在退出程序前多次输入新的表达式进行判定 //定义五种命题的连接词:或(-) 且(+) 非(!) 蕴含($) 等价(#) //定义两个命题的标点符号:'(',')' //定义三个原子公式:p,q,r
《数据结构,算法及应用》 zhangxianchao P80 13题
对于输入的一个中缀表达式,判断表达式是否合法。(表达式的输入符合四则运算的显示规范) 如果合法,把中缀表达式转换成一棵二叉树。(创建二叉链表,数据结构为二叉链表) 通过后序(根)遍历计算表达式的值,输出...
1. 题目:对输入的表达式判断其是否是合法的命题公式 2. 要求:有关命题公式的定义,请严格使用我们使用的教材上的定义。五种联接词的规定如下: 非:! 与:+ 或:- 蕴含:$ 等价:#
编写一个算法判断输入的表达式中括号是否配对(例如:exp=“([])}>”)。
对于输入的一个中缀表达式,判断表达式是否合法。(表达式的输入符合四则运算的显示规范) 如果合法,把中缀表达式转换成一棵二叉树。(创建二叉链表,数据结构为二叉链表) 通过后序(根)遍历计算表达式的值,输出...
易语言日期合法性正则表达式源码,日期合法性正则表达式,日期是否合法
判断给定表达式中的括号是否匹配,表达式中的合法括号为”(“, “)”, “[", "]“, “{“, ”}”,这三个括号可以按照任意的次序嵌套使用。
易语言日期合法性正则表达式.rar 易语言日期合法性正则表达式.rar 易语言日期合法性正则表达式.rar 易语言日期合法性正则表达式.rar 易语言日期合法性正则表达式.rar 易语言日期合法性正则表达式.rar
java用正则表达式判断电子邮件地址是否合法
MAC地址合法性检测(C,C++, JAVA实现)
利用正则表达式判断手机号码是否合法,对于一些需要手机验证的app有所帮助
《正则表达式经典实例》讲解了基于8种常用的编程语言使用正则表达式的经典实例。书中提供了上百种可以在实战中使用的实例,以帮助读者使用正则表达式来处理数据和文本。对于如何使用正则表达式来解决性能不佳、误报...
主要介绍了详解Java判断是否是整数,小数或实数的正则表达式,非常具有实用价值,需要的朋友可以参考下。
正则表达式中的特殊字符 字符 含意 \ 做为转意,即通常在"\"后面的字符不按原来意义解释,如/b/匹配字符"b",当b前面加了反斜杆后/\b/,转意为匹配一个单词的边界。 -或- 对正则表达式功能字符的还原,如"*"匹配它...