Naeioi

量子の風
随笔 - 8, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

2011年10月22日

栈-表达式求值

   所谓表达式求值就是用计算机计算加减乘除式子,说的装逼一点,就是计算中缀表达式的值。
   5 + ((1 + 2) * 4) − 3
   我们把这个式子添上括号,保持计算顺序不变。
   (5+((1+2)*4))-3)
   运算符夹在数字中间,“中缀”之名由此得来。
   人脑可以很快判断计算先后顺序,其实这个过程不是那么显然。因为*/+-有优先级,括号的加入又会打破这个规则。我们可以找出一个式子中最后进行的一步运算,对它的两边分别计算,在根据运算符进行合并。
   (5+((1+2)*4))-3)
  
下面挂的代码是递归实现的。不要骂我标题党,不久会更新真正的栈实现代码,这需要时间,时间~再说递归才符合思维习惯,也更便于记忆~!//表达式求值(递归实现) 
/*Author:naeioi
Prog:C++ 
Time:11.10.22
*/
#include <cstdio>
#include <cstring>
using namespace std;

const int maxl=100;
char s[maxl];

#define isnum(a) (a>='0'&&a<='9')
#define isop(a) (a=='+'||a=='-'||a=='*'||a=='/')

int match(int i)
{
    int count=1;
    while(count!=0){
          i++;
          if(s[i]=='(') ++count;
          if(s[i]==')') --count;
    }
    return i;
}

int ston(int p)//下标从p开始
{
    int ans=0,positive=1;//符号 
    if(s[p]=='-'){++p; positive=-1;}
    while(isnum(s[p])){
          ans*=10;
          ans+=s[p++]-'0';
    }
    return ans*positive;;
}

int div(int l,int r)//求l~r(下标)表示的式子的值 
{
    while(s[l]=='('&&match(l)==r){++l; --r;}//去除多余括号。不能写成s[l]=='('&&s[r]=')',形如(1+2)*(3+4)的式子会错误 
    if(l>r) return 0;
    
    int pos,prior=3;//优先级,2==*/,1==+-
    for(int i=l;i<=r;i++){//找优先级最小的运算符 
        if(s[i]=='(')
           if((i=match(i)+1)>r)
              break;
        if(s[i]=='*'||s[i]=='/')
        {  if(prior>=2){pos=i; prior=2;}}
        else if(s[i]=='+'||s[i]=='-')
                if(prior>=1&&i!=l&&!isop(s[i-1])){pos=i; prior=1;}//-接在运算符后时看成符号。否则看成减号 
    }
    
    if(prior==3)//是一个数
       return ston(l); 
    
    int a=div(l,pos-1),b=div(pos+1,r),ans;
    switch(s[pos])
    {
                  case '+':
                       ans=a+b;
                       break;
                  case '-':
                       ans=a-b;
                       break;
                  case '*':
                       ans=a*b;
                       break;
                  case '/':
                       ans=a/b;
                       break;
    }
    return ans;
}

int main()
{
    freopen("eval.in","r",stdin);
    freopen("eval.out","w",stdout);
    
    scanf("%s",s);
    
    printf("%d",div(0,strlen(s)-1));
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

posted @ 2011-10-22 23:12 Naeioi Zhu 阅读(322) | 评论 (0)编辑 收藏

2011年10月21日

基本数据结构-高精度

    下个月NOIP复试。初三一年奋战中考直升考,OI基本停滞。暑假宅在家里沉静于异世界也没怎么打代码,只帮人调了几个简单的程序,手生疏得很。于是打算用剩下一个月时间复习基本代码,建立一个标准代码库,让自己重新熟悉那些最最经典的算法实现,同时也为日后编码提供方便。
   这个标准代码库我都会亲自编码调试,努力保证正确性,力求简洁易读,注释完整。BUG在所难免,希望大家能在回复中帮助我改进XD.日后会不断更新各个方面(主要是涉及NOI)的基本代码。下面是预计的代码目录。
——————————————————————————————————————————————
1.基本数据结构
   高精
   二分
   哈希(也算查找)
   并查集
   队列、栈
      表达式计算
2.排序、查找
   堆
   快排
   归并排序
   选排、插排、冒排(冒牌………)
   基数排序
3.图论
   宽度、深度优先遍历
   Dijkstra、Floyd
   Prim、Kruskal
   SPFA
   最大流&最小最小费用最大流
4.其他
(未完待补充)
——————————————————————————————————————————————————
高精度模板(无压位)
//高精无压位
/*
Author:naeioi
Prog:C++
Time:11-10-20
*/
#include 
<cstdio>
#include 
<string.h>
//#include <conio.h>
using namespace std; 

const int maxlen=105+1;
#ifndef max
        
#define max(a,b) ((a)>(b)?a:b)
#endif
/*结构说明 
1.len代表实际长度
2.s[]从1开始 逆序存储 
3.默认长度105 
*/
/*注意事项
1.一定要将clear()函数放在赋值函数头,将数据清零
2. 赋值运算符优先级低,跟比较运算符在一起注意打括号
3.基本函数定义形式
   Bign operator *(const Bign &b)const{}
   注意返回Bign以及那两个const防改写 
4. 函数都应写在struct里面
*/

struct Bign{//函数后打//的是二级函数 
       int len,s[maxlen];
       
//函数部分 
       
//初始化
       void clear(){len=1;memset(s,0,sizeof(s));}//必要,赋值前必须清空 
       Bign(){clear();}
       
//赋值
       Bign operator = (const char *a){
            clear();
//只需在此clear(),其他所有赋值函数都要调用它 
            len=strlen(a);
            
for(int i=1;i<=len;i++)
                    s[i]
=a[len-i]-'0';
            
return *this;
       }
       Bign 
operator = (int num){//用sprintf巧妙转化,减少代码量 
            char tmp[maxlen];
            sprintf(tmp,
"%d",num);
            
return *this=tmp;
       }
       
       Bign(
int num){*this=num;}//
       Bign(const char *a){*this=a;}//
       
       
//运算符
       
//c++备注:形参const表示不改变形参,末尾const表示不改变*this.运算返回bign供操作
        Bign operator + (const Bign &b)const{
             Bign c
=*this;
             c.len
=max(len,b.len);
             
for(int i=1;i<=c.len;i++)
                     
if((c.s[i]+=b.s[i]) >= 10){//!!!赋值运算符比比较运算符优先度低!!! 
                        c.s[i+1]+=c.s[i]/10;
                        c.s[i]
%=10;
                     }
             
if(c.s[c.len+1]>0) c.len++;
             
return c;
        }
        Bign 
operator += (const Bign &b){
             
return (*this=*this+b);
        }
//
        Bign operator + (int b)const{
             Bign t
=b;
             
return t+*this;
        }
//
        Bign operator - (const Bign &b)const{//须保证b比*this小 
             Bign c=*this;
             
for(int i=1;i<=len;i++)
                     
if((c.s[i]-=b.s[i]) < 0){
                        c.s[i
+1]--;
                        c.s[i]
+=10;
                     }
             
while(c.s[c.len]==0) c.len--;
             
return c;
        }
        Bign 
operator - (int b)const{
             Bign t
=b;
             
return *this-t;
        }
//
        Bign operator * (const Bign &b)const{
             Bign c;
             c.len
=len+b.len;
             
             
for(int i=1;i<=len;i++)
                     
for(int j=1;j<=b.len;j++)
                             
if((c.s[i+j-1]+=s[i] * b.s[j]) >= 10){
                                c.s[i
+j]+=c.s[i+j-1]/10;
                                c.s[i
+j-1]%=10;
                             }
             
if(c.s[c.len]==0) c.len--;
             
return c;
        }
        Bign 
operator *= (const Bign &b){
             
return (*this=*this*b);
        }
//
        Bign operator / (int b)const{//必须整除(TODO:另用函数实现取余)
             Bign t=*this,c;
             c.len
=len;
             
for(int i=len;i>=1;i--){
                 t.s[i
-1]+=(t.s[i]%b)*10;
                 c.s[i]
=t.s[i]/b;
             }
             
while(c.s[c.len]==0) c.len--;
             
             
//remain=t.s[0];
             return c;
        }
        
int operator % (int b)const{
             Bign t
=*this,c;
             c.len
=len;
             
for(int i=len;i>=2;i--){
                 t.s[i
-1]+=(t.s[i]%b)*10;
                 t.s[i
-1]%=b;//优化防溢出 
             }
             
return t.s[1]%b;
        }
        
//大小比较
        bool operator > (const Bign &b)const{
             
if(len>b.len)
                 
return 1;
             
else if(len<b.len)
                     
return 0;
             
else{
                  
for(int i=len;i>=1;i--)
                      
if(s[i]>b.s[i])
                         
return 1;
                  
return 0;
             }
        } 
        
bool operator > (int b)const{
             Bign t
=b;
             
return *this>t;
        }
//
        
        
//输出并换行 
        void print(){
             
for(int i=len;i>=1;i--)
                     printf(
"%d",s[i]);
             printf(
"\n");
        }
};
//OK

posted @ 2011-10-21 20:13 Naeioi Zhu 阅读(160) | 评论 (0)编辑 收藏

2010年11月12日

UVa 10115

原题在这里.小心指针!!!
#include <cstdio>
#include <string.h>
using namespace std;

const int maxn=15,maxl=300;
char key[2][maxn][maxl],str[maxl];
int l[maxn],N;

bool match(char *s,char *k)
{
    while (*k)
    {
        if (*s!=*k)
            return false;
        ++s;
        ++k;
    }
    return true;
}

void replace(int cur,int i)
{
    char tmp[maxl]= {0};
    memcpy(tmp,str,cur);
    strcat(tmp,key[1][i]);
    strcat(tmp,str+cur+l[i]);
    memcpy(str,tmp,sizeof(str));
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10115.in","r",stdin);
    freopen("10115.out","w",stdout);
#endif

    while (scanf("%d",&N)&&N!=0)
    {
        memset(str,0,sizeof(str));
        getchar();
        for (int i=0; i<N; i++)
        {
            gets(key[0][i]);
            gets(key[1][i]);
            l[i]=strlen(key[0][i]);
        }
        gets(str);
        for (int i=0; i<N; i++)
            for (int j=0; str[j+l[i]-1]; j++)
                if (match(str+j,key[0][i]))
                {
                    replace(j,i);
                    j=0;
                }
        puts(str);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}

posted @ 2010-11-12 21:46 Naeioi Zhu 阅读(177) | 评论 (0)编辑 收藏

UVa 644

这道题交了4遍才AC,也不懂是什么原因
#include <cstdio>
#include <string.h>
using namespace std;

const int maxn=20;
char a[maxn][maxn],tmp[maxn];
int tot=-1,count=0;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("644.in","r",stdin);
    freopen("644.out","w",stdout);
#endif


    while (scanf("%s",a[++tot])==1)
    {
        if (a[tot][0]!='9')continue;
        bool is=true;
        --tot;
        for (int i=0; i<=tot&&is; i++)
            for (int j=0; j<=tot&&is; j++)
                if (i!=j&&strlen(a[j])>=strlen(a[i]))
                {
                    sprintf(tmp,"%.*s",strlen(a[i]),a[j]);
                    if (strcmp(tmp,a[i])==0)
                        is=false;
                }
        printf("Set %d is ",++count);
        if (is)
            printf("immediately decodable\n");
        else printf("not immediately decodable\n");
        tot=-1;
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}

posted @ 2010-11-12 20:32 Naeioi Zhu 阅读(209) | 评论 (0)编辑 收藏

UVa 10815

原题在这里。代码写的比较乱
#include <cstdio>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
using namespace std;

const int maxn=5005,maxl=205;
int tot=0;
char word[maxn][maxl],now[maxl];

bool find(void)
{
    for (int i=0; i<tot; i++)
        if (!strcmp(now,word[i]))
            return true;
    return false;
}

int cmp(const void *a,const void *b)
{
    return strcmp((char*)a,(char*)b);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10815.in","r",stdin);
    freopen("10815.out","w",stdout);
#endif

    for (;;)
    {
        do
        {
            *now=getchar();
        }
        while (!isalpha(*now)&&*now!=EOF);
        now[1]=0;
        if (scanf("%[qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM]",now+1)==EOF)
            break;
        for (int i=0; now[i]; i++)
            now[i]=tolower(now[i]);
        if (!find())
            memcpy(word[tot++],now,sizeof(now));
    }

    qsort(word,tot,sizeof(word[0]),cmp);

    for (int i=0; i<tot; i++)
        printf("%s\n",word[i]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}

posted @ 2010-11-12 19:13 Naeioi Zhu 阅读(269) | 评论 (0)编辑 收藏

2010年11月11日

Uva 409

原题在这里。字符串匹配,写起来稍稍有些繁琐

1 #include <cstdio> 2 #include <string.h> 3 #include <ctype.h> 4 #include <vector> 5 using namespace std; 6 7 const int maxk=100,maxl=100; 8 char key[maxk][maxl],str[maxl],str2[maxl],ans[maxk][maxl]; 9 int K,E,n=0,Max,l; 10 11 bool find(int x,int y) 12 { 13 for(int i=0;i<K;i++){ 14 int j; 15 for(j=0;x+j<=y&&key[i][j];j++) 16 if(str[x+j]!=key[i][j]) 17 break; 18 if(x+j>y&&!key[i][j]) 19 return true; 20 } 21 return false; 22 } 23 24 int main() 25 { 26 #ifndef ONLINE_JUDGE 27 freopen("409.in","r",stdin); 28 freopen("409.out","w",stdout); 29 #endif 30 31 while(scanf("%d%d",&K,&E)==2){ 32 l=Max=0; 33 printf("Excuse Set #%d\\n",++n); 34 getchar(); 35 36 for(int i=0;i<K;i++) 37 gets(key[i]); 38 for(int i=0;i<E;i++){ 39 scanf("%[^\\r\\n]",str); 40 memcpy(str2,str,sizeof(str)); 41 getchar(); 42 int a=0,b,count=0; 43 while(str[a]){ 44 while(!isalpha(str[a])&&str[a])++a; 45 b=a; 46 while(isalpha(str[b])){str[b]=tolower(str[b]);++b;} 47 if(find(a,b-1))count++; 48 a=b; 49 } 50 if(count>Max){ 51 Max=count; 52 memset(ans,0,sizeof(ans)); 53 l=1; 54 memcpy(ans[l-1],str2,sizeof(str)); 55 } 56 else if(count==Max) 57 memcpy(ans[l++],str2,sizeof(str)); 58 } 59 for(int i=0;i<l;i++) 60 printf("%s\\n",ans[i]); 61 printf("\\n"); 62 } 63 64 fclose(stdin); 65 fclose(stdout); 66 return 0; 67 } 68

posted @ 2010-11-11 19:19 Naeioi Zhu 阅读(292) | 评论 (0)编辑 收藏

2010年11月10日

UVa 537

没什么好说的,锻炼编程能力,注意善用scanf :)
1 #include <cstdio> 2 using namespace std; 3 4 int N; 5 double a[260]; 6 7 int main() 8 { 9 #ifndef ONLINE_JUDGE 10 freopen("537.in","r",stdin); 11 freopen("537.out","w",stdout); 12 #endif 13 14 scanf("%d",&N); 15 getchar(); 16 17 for(int i=1;i<=N;i++){ 18 a['U']=a['I']=a['P']=0.0; 19 for(int j=0;j<=1;j++){ 20 char last=getchar(),now; 21 while((now=getchar())!='=')last=now; 22 scanf("%lf%c",&a[last],&now); 23 switch(now){ 24 case 'm': 25 a[last]/=1000.0; 26 break; 27 case 'k': 28 a[last]*=1000.0; 29 break; 30 case 'M': 31 a[last]*=1000000.0; 32 break; 33 } 34 } 35 36 printf("Problem #%d\\n",i); 37 38 if(a['U']&&a['I']) 39 printf("P=%.2lfW",a['U']*a['I']); 40 else if(a['U']&&a['P']) 41 printf("I=%.2lfA",a['P']/a['U']); 42 else if(a['I']&&a['P']) 43 printf("U=%.2lfV",a['P']/a['I']); 44 printf("\\n\\n"); 45 } 46 47 fclose(stdin); 48 fclose(stdout); 49 return 0; 50 } 51

posted @ 2010-11-10 19:08 Naeioi Zhu 阅读(314) | 评论 (0)编辑 收藏

2010年11月7日

UVa 10010

  在一个n*m的字符矩阵中寻找给定的字符串,字符串可以是上下、下上、左右、右左等8个方向。输出每个字符串第一个字符首次出现的位置。
要注意的是换行问题,对一个少一个都判作WA
1 #include <cstdio> 2 #include <string.h> 3 #include <ctype.h> 4 using namespace std; 5 6 const int maxn=60,dx[]= {1,1,1,0,-1,-1,-1,0},dy[]= {-1,0,1,1,1,0,-1,-1}; 7 char G[maxn][maxn]; 8 int N,M,K; 9 10 int main() 11 { 12 #ifndef ONLINE_JUDGE 13 freopen("10010.in","r",stdin); 14 freopen("10010.out","w",stdout); 15 #endif 16 17 int C,t=0; 18 scanf("%d",&C); 19 20 while(C--) { 21 if(t!=0)printf("\\n"); 22 ++t; 23 24 scanf("%d%d",&N,&M); 25 for(int i=1; i<=N; i++) 26 for(int j=1; j<=M; j++) { 27 char tmp; 28 do { 29 tmp=getchar(); 30 } 31 while(!isalpha(tmp)); 32 G[i][j]=tolower(tmp); 33 } 34 35 scanf("%d",&K); 36 getchar(); 37 while(K--) { 38 char str[maxn]; 39 gets(str); 40 int len=strlen(str); 41 42 for(int i=0; i<len; i++) 43 str[i]=tolower(str[i]); 44 45 bool ok=false; 46 for(int i=1; i<=N&&!ok; i++) 47 for(int j=1; j<=M&&!ok; j++) 48 for(int k=0; k<8&&!ok; k++) { 49 int x=i,y=j,count=0; 50 while(x>=1&&y>=1&&x<=N&&y<=M&&count<len&&str[count]==G[x][y]) { 51 ++count; 52 x+=dx[k]; 53 y+=dy[k]; 54 } 55 if(count==len) { 56 ok=true; 57 printf("%d %d\\n",i,j); 58 } 59 } 60 } 61 //printf("\\n"); 62 } 63 64 fclose(stdin); 65 fclose(stdout); 66 return 0; 67 } 68

posted @ 2010-11-07 16:36 Naeioi Zhu 阅读(425) | 评论 (0)编辑 收藏