C++博客-Naeioi

栈-表达式求值

Naeioi Zhu — Sat, 22 Oct 2011 15:12:00 GMT

所谓表达式求值就是用计算机计算加减乘除式子，说的装逼一点，就是计算中缀表达式的值。
5 + ((1 + 2) * 4) − 3
我们把这个式子添上括号，保持计算顺序不变。
(5+((1+2)*4))-3)
运算符夹在数字中间，“中缀”之名由此得来。
人脑可以很快判断计算先后顺序，其实这个过程不是那么显然。因为*/+-有优先级，括号的加入又会打破这个规则。我们可以找出一个式子中最后进行的一步运算，对它的两边分别计算，在根据运算符进行合并。
(5+((1+2)*4))-3)

下面挂的代码是递归实现的。不要骂我标题党，不久会更新真正的栈实现代码，这需要时间，时间~再说递归才符合思维习惯，也更便于记忆~！//表达式求值（递归实现）

/*Author:naeioi
Prog:C++
Time:11.10.22
*/
#include
#include
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;
}

Naeioi Zhu 2011-10-22 23:12 发表评论

基本数据结构-高精度

Naeioi Zhu — Fri, 21 Oct 2011 12:13:00 GMT

下个月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
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

Naeioi Zhu 2011-10-21 20:13 发表评论

UVa 10115

Naeioi Zhu — Fri, 12 Nov 2010 13:46:00 GMT

原题在这里.小心指针!!!

#include

#include

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;

Naeioi Zhu 2010-11-12 21:46 发表评论

UVa 644

Naeioi Zhu — Fri, 12 Nov 2010 12:32:00 GMT

这道题交了4遍才AC,也不懂是什么原因

#include

#include

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;

Naeioi Zhu 2010-11-12 20:32 发表评论

UVa 10815

Naeioi Zhu — Fri, 12 Nov 2010 11:13:00 GMT

原题在这里。代码写的比较乱

#include

#include

#include

#include

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;

Naeioi Zhu 2010-11-12 19:13 发表评论

Uva 409

Naeioi Zhu — Thu, 11 Nov 2010 11:19:00 GMT

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

 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

Naeioi Zhu 2010-11-11 19:19 发表评论

UVa 537

Naeioi Zhu — Wed, 10 Nov 2010 11:08:00 GMT

没什么好说的，锻炼编程能力，注意善用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

Naeioi Zhu 2010-11-10 19:08 发表评论

UVa 10010

Naeioi Zhu — Sun, 07 Nov 2010 08:36:00 GMT

在一个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

Naeioi Zhu 2010-11-07 16:36 发表评论