codevs 1107 等价表达式
2005年NOIP全国联赛提高组
明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质:
1.表达式只可能包含一个变量‘a’。
2.表达式中出现的数都是正整数,而且都小于10000。
3.表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符)
4.幂指数只可能是1到10之间的正整数(包括1和10)。
5.表达式内部,头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子:
((a^1)^2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1+(a-1)^3,1^10^9……
输入第一行给出的是题干中的表达式。第二行是一个整数n(2<=n<=26),表示选项的个数。后面n行,每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D……
输入中的表达式的长度都不超过50个字符,而且保证选项中总有表达式和题干中的表达式是等价的。
输出包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。
(a+1)^2
3
(a-1)^2+4*a
a+1+a
a^2+2*a*1+1^2+10-10+a-a
AC
【数据规模】
对于30%的数据,表达式中只可能出现两种运算符‘+’和‘-’;
对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’在表达式中都可能出现。
对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。
/*
机智的方法:给a代入特殊值。不要代入0,1,-1这样的数。最好代质数。
只代入一个数还是很有可能出现两个不等的式子算出来结果相等。
多代几个数
还有一个问题,代数的话,计算结果可能会超过long long范围。
计算的时候记得模一个大质数
因为我们取了若干个数代进去,所以即使模了一个数冲突的几率也很小
下面进入正题:如何计算表达式的值?
我们需要开两个栈:一个用来存储数字,一个用来存储符号。
读入数字时,压入数字栈
读入符号时:
1.如果是运算符,当前栈顶的运算符优先级大于等于新运算符,则将栈顶运算符弹出,并将当前数字栈顶的两个数进行相应运算,弹出旧数,压入新结果。不停循环,直到栈里面没有符号或符号优先级低于当前新运算符。
2.如果是(,直接压入栈。
3.如果是),则依次将栈里面的符号弹出,并计算。直到遇到一个(。 */
#include<cstring>
#include<iostream>
using namespace std;
#include<cstdio>
#define mod 32767
#define max_len 10
#define L 55
char s[L],b[L],n;
int ans[max_len+];
int sumstack[L],fhstack[L];
int len1=,len2=;
int quick_mod(int x,int y)//x^y
{
int ret=;
while(y)
{
if(y&)
{
ret*=x;
ret%=mod;
}
y>>=;x*=x;
x%=mod;
}
return ret;
}
void multi()
{
switch(fhstack[len2])
{
case :sumstack[len1-]+=sumstack[len1];
sumstack[len1-]%=mod;
break;
case :sumstack[len1-]-=sumstack[len1];
sumstack[len1-]%=mod;
break;
case :sumstack[len1-]*=sumstack[len1];
sumstack[len1-]%=mod;
break;
case :sumstack[len1-]=quick_mod(sumstack[len1-],sumstack[len1]);
sumstack[len1-]%=mod;
break;
case :len2--; return;/*遇到左括号,直接跳过,是符号栈指针--*/
}
len1--;len2--;
}
int js(char s1[],int k)
{
memset(sumstack,,sizeof(sumstack));
memset(fhstack,,sizeof(fhstack));
sumstack[]=;len1=;
len2=;
int len=strlen(s1);
for(int i=;i<len;++i)
{
if(s1[i]==' ') continue;
if(s1[i]=='a')
{
sumstack[++len1]=k;
continue;
}
if(s1[i]>=''&&s1[i]<='')
{
sumstack[++len1]=s1[i]-'';
while(s1[i+]>=''&&s1[i+]<='')
{
sumstack[len1]=sumstack[len1]*+s1[i+]-'';
sumstack[len1]%=mod;
i++;
}
continue;
}
switch(s1[i])
{
case '(': fhstack[++len2]=;break;
case '+':while(len2>&&fhstack[len2]>&&fhstack[len2]<) multi();
fhstack[++len2]=;
break;
/*注意这里的是while,不是if,就是如果满足条件的话,就把前面的一直算*/
case '-':while(len2>&&fhstack[len2]>&&fhstack[len2]<) multi();
fhstack[++len2]=;
break;
case '*':while(len2>&&fhstack[len2]>&&fhstack[len2]<) multi();
fhstack[++len2]=;
break;
case '^':while(len2>&&fhstack[len2]>&&fhstack[len2]<) multi();
fhstack[++len2]=;
break;
case ')':while(len2>&&fhstack[len2]<) multi();
if(fhstack[len2]==) len2--;
break;
}
}
while(len2) multi();
if(len1==) return (sumstack[]+mod)%mod;
return (sumstack[]+mod)%mod;
}
int main()
{
gets(s);
for(int i=;i<max_len;++i)
ans[i]=js(s,i);
scanf("%d\n",&n);
for(int i=;i<=n;++i)
{
gets(b);
bool flag=true;
for(int i=;i<max_len;++i)
{
int x=js(b,i);
if(x!=ans[i])
{
flag=false;
break;
}
}
if(flag)
printf("%c",'A'-+i);
}
return ;
}
数据结构--栈 codevs 1107 等价表达式的更多相关文章
-
codevs 1107 等价表达式
传送门 题解:第一眼这题好像非常难得样子,简直没有思路.但是这可以用栈带入特殊值来解决.这里用到两个栈,一个是存贮数字,另一个存贮运算符,按优先级进行运算.当读入的运算符比运算符栈的栈顶元素优先级低时 ...
-
等价表达式 2005年NOIP全国联赛提高组(栈模拟)
P1054 等价表达式 题目描述 明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的 ...
-
洛谷 P1054 等价表达式 解题报告
P1054 等价表达式 题目描述 明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的 ...
-
javascript使用栈结构将中缀表达式转换为后缀表达式并计算值
1.概念 你可能听说过表达式,a+b,a+b*c这些,但是前缀表达式,前缀记法,中缀表达式,波兰式,后缀表达式,后缀记法,逆波兰式这些都是也是表达式. a+b,a+b*c这些看上去比较正常的是中缀表达 ...
-
等价表达式(noip2005)
3.等价表达式 [问题描述] 兵兵班的同学都喜欢数学这一科目,中秋聚会这天,数学课代表给大家出了个有关代数表达式的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也 ...
-
数据结构——栈(C语言实现)
#include <stdio.h> #include <stdlib.h> #include<string.h> #include<malloc.h> ...
-
C++ 泛型 编写的 数据结构 栈
平时编程里经常需要用到数据结构,比如 栈和队列 等, 为了避免每次用到都需要重新编写的麻烦现将 C++ 编写的 数据结构 栈 记录下来,以备后用. 将 数据结构 栈 用头文件的形式 ...
-
栈应用之 后缀表达式计算 (python 版)
栈应用之 后缀表达式计算 (python 版) 后缀表达式特别适合计算机处理 1. 中缀表达式.前缀表达式.后缀表达式区别 中缀表达式:(3 - 5) * (6 + 17 * 4) / 3 17 ...
-
C语言数据结构-栈的实现-初始化、销毁、长度、取栈顶元素、查找、入栈、出栈、显示操作
1.数据结构-栈的实现-C语言 #define MAXSIZE 100 //栈的存储结构 typedef struct { int* base; //栈底指针 int* top; //栈顶指针 int ...
随机推荐
-
PHP文件大小格式化函数合集
比如碰到一个很大的文件有49957289167B,大家一看这么一长串的数字后面单位是字节B,还是不知道这个文件的大小是一个什么概念,我们把它转换成GB为单位,就是46.53GB.用下面这些函数就可以完 ...
-
Hello Java
用记事本或者Eclipse编写如下代码 public class JavaAPP{ public static void main(String[] args){ System ...
-
C# 调用百度地图Web服务API
最近公司项目中需要根据两个地点的交通路径和距离做一些数据推荐,为了程序的稳定和用户体验所以想从百度地图 API 采集数据保存到数据库中,经过一翻研究之后选定了百度地图 Web 服务 API 中的 Di ...
-
搭建SpringMVC+MyBatis开发框架一
大部分 Java 应用都是 Web 应用,展现层是 Web 应用不可忽略的重要环节.Spring 为展现层提供了一个优秀的 Web 框架—— Spring MVC.和众多其他 Web 框架一样,它基于 ...
-
c++常用IDE
vs2013. CodeLite (c/c++/PHP) codeBlocks Qt Creator Xcode
-
云信推送通知 APN invalid Token
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #e4af09; min-height: 14.0px } ...
-
JAVA_将唐诗按照古文样式输出
1. 如有唐诗: 锄禾日当午 汗滴禾下土 谁知盘中餐 粒粒皆辛苦 要求将这首唐诗按照古文样式输出,输出格式如下: 粒谁汗锄 粒知滴禾 皆盘禾日 辛中下当 苦餐土午 public class Text ...
-
[转帖]ASP.NET的版本?
ASP.NET的版本? https://www.cnblogs.com/guogangj/p/8526365.html 问题源于这么一本书: <ASP.NET 4 解密(卷1)>,这本书大 ...
-
[UE4]在AIController中使用行为树
行为树会在Root根下面的每个子节点中从左右到右来回往复循环执行.
-
2013成都网赛1003 hdu 4730	We Love MOE Girls
题意:有一个字符串,若以"desu"结尾,则将末尾的"desu"替换为"nanodesu",否则在字符串末尾加上"nanodesu ...