天之道

括号匹配

在处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：

( ) [ ( ) ( [ ] ) ] { }

1 2 3 4 5 6 7 8 9 10 11 12

从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：

1、当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。

2、当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除

3、若到最后，括号不能完全匹配，则说明输入的表达式有错

Input

第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入

Output

对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error

Sample Input

2

(a+b)[4*5+(-6)]

[5*8]/{(a+b)-6

Sample Output

ok

error

代码：

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int main()
{
    int t,len;
    stack<char> mystack;
    cin>>t;
    while(t--)
    {
        int ok=0;
        char str[100];
        cin>>str;
        len=strlen(str);
        for(int i=0;i<len;i++)
        {
           switch(str[i])
           {
              case '(':
              case '[':
              case '{':
                  mystack.push(str[i]);
                  break;
              case ')':
                  if(mystack.top() == '(')
                  {
                      mystack.pop();
                      ok=1;
                  }
                  break;
              case ']':
                  if(mystack.top() == '[')
                  {
                      mystack.pop();
                      ok=1;
                  }
                  break;
              case '}':
                  if(mystack.top() == '{')
                  {
                      mystack.pop();
                      ok=1;
                  }
                  break;
              default: break;
           }
        }
        if(ok && mystack.empty())
            cout<<"ok"<<endl;
        else
            cout<<"error"<<endl;
    }

    return 0;
}

posted @ 2012-09-13 15:11 hoshelly 阅读(1865) | 评论 (0) | 编辑收藏

数制转换

Description

对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换

整数部分19，小数部分0.125

19 / 2 = 9 … 1 0.125 * 2 = 0.25 … 0

9 / 2 = 4 … 1 0.25 * 2 = 0.5 … 0

4 / 2 = 2 … 0 0.5 * 2 = 1 … 1

2 / 2 = 1 … 0

1 / 2 = 0 … 1

所以整数部分转为 10011，小数部分转为0.001，合起来为10011.001 请用堆栈实现上述数制转换

Input

第一行输入一个t，表示下面将有t组测试数据。

接下来的t行的每行包含两个参数n（0<n<10000，且最多有8位小数）和k（1<k<=16），n表示要转换的数值，n可以带小数（也可以不带！），k表示要转换的数制，k必须是正整数。大于10的进制数据用A\B\C\D\E\F表示

Output

对于每一组测试数据，每行输出转换后的结果，小数部分大于8位的，只输出前8位小数

Sample Input

2

19.125 2

15.125 16

Sample Output

10011.001

F.2

代码
#include<iostream>

#include<stack>
using namespace std;
int main()
{
    stack<int> mystack;
    int t,m,k;
    double b,a;
    cin>>t;
    while(t--)
    {
        int c,x[100],d=0,i=0,count=0;
        cin>>b>>k;
        m=b;
        a=b-m;
        while(m)
        {
            c=m%k;
            m=m/k;
            mystack.push(c);
        }
        while(1)
        {
            d=a*k;
            if(d>=k)
                break;
            a=a*k;
            x[i++]=d;
            count++;
        }

        while(!mystack.empty())
        {
            if(mystack.top()<10)
            {
                cout<<mystack.top();
                mystack.pop();
            }
            else
            {
                switch(mystack.top())
                {
                  case 10: cout<<"A"; mystack.pop(); break;
                  case 11: cout<<"B"; mystack.pop(); break;
                  case 12: cout<<"C"; mystack.pop(); break;
                  case 13: cout<<"D"; mystack.pop(); break;
                  case 14: cout<<"E"; mystack.pop(); break;
                  case 15: cout<<"F"; mystack.pop(); break;
                }
            }
        }


        cout<<".";
        for(i=0;i<count;i++)
            cout<<x[i];
        cout<<endl;

    }
    return 0;
}

posted @ 2012-09-13 15:10 hoshelly 阅读(285) | 评论 (0) | 编辑收藏

十进制转二进制（代码）

如下：
#include<stdio.h>

int main()
{
    int M,b;
    int N[100],c=0;
    scanf("%d%d",&b,&M);//输入进制b(2~10),要转化为b进制的正整数M(十进制)
    while(M)
    {
        N[c++]=M%b;
        M=M/b;
    }
    for(int i=c-1;i>=0;i--)
        printf("%d",N[i]);
    printf("\n");
    return 0;
}

posted @ 2012-09-08 12:41 hoshelly 阅读(717) | 评论 (0) | 编辑收藏

二进制转十进制（代码）

如下：
#include<stdio.h>

#include<string.h>
#include<math.h>
int main()
{
    char M[100]={0};
    int N=0;
    gets(M);
    int len=strlen(M);
    for(int i=0;i<len;i++)
    {
        N+=(M[i]-'0') * pow(2.0,len-i-1);
    }
    printf("%d\n",N);
    return 0;
}

posted @ 2012-09-08 12:37 hoshelly 阅读(1689) | 评论 (0) | 编辑收藏

求两个线性表的集合

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
    ElemType *elem; //存储空间基址
    int length; //当前的线性表长度
    int listsize; //当前分配的存储容量
}SqList;

//初始化线性表
Status InitList_Sq(SqList *L) //用线性表的指针操作
{
    (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}
int ListLength(SqList L)
{
    return L.length;
}

Status GetElem(SqList L,int i,ElemType *e)
{
    if(i<1 || i>L.length)
        exit(ERROR);
    *e=*(L.elem+i-1);
    return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    ElemType *newbase,*p,*q;
    if(i<1 || i>(*L).length+1)
        return ERROR;
    if((*L).length >= (*L).listsize)
    {
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).elem=newbase;
        (*L).listsize +=LISTINCREMENT;
    }
    q=(*L).elem+i-1; //插入位置
    for(p=(*L).elem+(*L).length-1;p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++(*L).length;
    return OK;
}

int LocateElem(SqList L,ElemType e)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        if(*(L.elem+i) == e)
            break;
    }
    if(i>=L.length)
        return 0;
    return i+1;
}

Status Visit(ElemType *c)
{
    printf("%d ",*c);
    return OK;
}

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        Visit(L.elem+i);
    printf("\n");
    return OK;
}

void Union(SqList *La,SqList Lb) //求La和Lb中元素的集合La，即把Lb中与La不相同的元素取出来插入La中
{
    ElemType La_len,Lb_len;
    int i,e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);
        if(!LocateElem(*La,e))
            ListInsert(La,++La_len,e);
    }
}//Union
int main()
{
    SqList La,Lb;
    int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
    InitList_Sq(&La);
    for(j=1;j<=4;j++)
        ListInsert(&La,j,a[j-1]);
    printf("print La: \n");
    ListTraverse(La);

    InitList_Sq(&Lb);
    for(j=1;j<=7;j++)
        ListInsert(&Lb,j,b[j-1]);
    printf("print Lb: \n");
    ListTraverse(Lb);

    Union(&La,Lb);

    printf("print La: \n");
    ListTraverse(La);

    return 0;
}

posted @ 2012-08-21 22:38 hoshelly 阅读(182) | 评论 (0) | 编辑收藏

归并两个线性表得到新的线性表

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
    ElemType *elem; //存储空间基址
    int length; //当前的线性表长度
    int listsize; //当前分配的存储容量
}SqList;

//初始化线性表
Status InitList_Sq(SqList *L) //用线性表的指针操作
{
    (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}
int ListLength(SqList L)
{
    return L.length;
}

Status GetElem(SqList L,int i,ElemType *e)
{
    if(i<1 || i>L.length)
        exit(ERROR);
    *e=*(L.elem+i-1);
    return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    ElemType *newbase,*p,*q;
    if(i<1 || i>(*L).length+1)
        return ERROR;
    if((*L).length >= (*L).listsize)
    {
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).elem=newbase;
        (*L).listsize +=LISTINCREMENT;
    }
    q=(*L).elem+i-1; //插入位置
    for(p=(*L).elem+(*L).length-1;p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++(*L).length;
    return OK;
}

Status Visit(ElemType *c)
{
    printf("%d ",*c);
    return OK;
}

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        Visit(L.elem+i);
    printf("\n");
    return OK;
}

void MergeList(SqList La,SqList Lb,SqList *Lc) //归并线性表La和Lb得到新的线性表Lc,Lc的数据元素安置递减排列
{
    int i=1,j=1,k=0;
    int La_len,Lb_len;
    ElemType ai,bj;
    InitList_Sq(Lc);
    La_len=ListLength(La);
    Lb_len=ListLength(Lb);
    while((i<=La_len) && (j<=Lb_len)) //如果表La和表Lb都非空
    {
        GetElem(La,i,&ai);
        GetElem(Lb,j,&bj);
        if(ai<=bj)
        {
            ListInsert(Lc,++k,ai); ++i;
        }
        else
        {
            ListInsert(Lc,++k,bj); ++j;
        }
    }

    while(i<=La_len)  //如果只有La非空
    {
        GetElem(La,i++,&ai);
        ListInsert(Lc,++k,ai);
    }

    while(j<=Lb_len)
    {
        GetElem(Lb,j++,&bj);
        ListInsert(Lc,++k,bj);
    }
}
int main()
{
    SqList La,Lb,Lc;
    int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
    InitList_Sq(&La);
    for(j=1;j<=4;j++)
        ListInsert(&La,j,a[j-1]);
    printf("print La: \n");
    ListTraverse(La);

    InitList_Sq(&Lb);
    for(j=1;j<=7;j++)
        ListInsert(&Lb,j,b[j-1]);
    printf("print Lb: \n");
    ListTraverse(Lb);

    MergeList(La,Lb,&Lc);

    printf("print Lc: \n");
    ListTraverse(Lc);

    return 0;
}

posted @ 2012-08-21 21:51 hoshelly 阅读(290) | 评论 (0) | 编辑收藏

线性表基本操作

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
    ElemType *elem; //存储空间基址
    int length; //当前的线性表长度
    int listsize; //当前分配的存储容量
}SqList;

//初始化线性表
Status InitList_Sq(SqList *L) //用线性表的指针操作
{
    (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}
int ListLength(SqList L)
{
    return L.length;
}

Status ListEmpty(SqList L)
{
    if(L.length == 0)
        return OK;
    else
        return ERROR;
}

Status ClearList(SqList *L)
{
    (*L).length=0;
    return OK;
}

Status DestroyList(SqList *L)
{
    free((*L).elem);
    (*L).elem=NULL;
    (*L).length=0;
    (*L).listsize=0;
    return OK;
}

Status GetElem(SqList L,int i,ElemType *e)
{
    if(i<1 || i>L.length)
        exit(ERROR);
    *e=*(L.elem+i-1);
    return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    ElemType *newbase,*p,*q;
    if(i<1 || i>(*L).length+1)
        return ERROR;
    if((*L).length >= (*L).listsize)
    {
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).elem=newbase;
        (*L).listsize +=LISTINCREMENT;
    }
    q=(*L).elem+i-1; //插入位置
    for(p=(*L).elem+(*L).length-1;p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++(*L).length;
    return OK;
}

Status Visit(ElemType *c)
{
    printf("%d ",*c);
    return OK;
}

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        Visit(L.elem+i);
    printf("\n");
    return OK;
}

int LocateElem(SqList L,ElemType e)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        if(*(L.elem+i) == e)
            break;
    }
    if(i>=L.length)
        return 0;
    return i+1;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length == 0)
        return ERROR;
    if(i<1 || i>=L->length)
        return ERROR;
    *e=*(L->elem+i-1);
    if(i<L->length)
    {
        for(k=i;k<L->length;k++)
            *(L->elem+k-1)=*(L->elem+k);
    }
    L->length--;
    return OK;
}

int main()
{
    int i,e;
    SqList mylist;
    int m = InitList_Sq(&mylist);
    if(m)
    {
        printf("线性表创建成功!\n");
        printf("当前表长: %d \n",ListLength(mylist));
    }
    else
        printf("线性表创建失败.");
    for(i=1;i<=10;i++)
        ListInsert(&mylist,i,i);
    ListTraverse(mylist);
    printf("当前表长：%d \n",ListLength(mylist));
    GetElem(mylist,5,&e);
    printf("第5个元素为：%d\n",e);
    ListDelete(&mylist,4,&e);
    printf("删除第4个元素后：");
    ListTraverse(mylist);
    printf("当前表长：%d \n",ListLength(mylist));
    i=ClearList(&mylist);
    printf("清空线性表后：表长为 %d\n",mylist.length);
    i=ListEmpty(mylist);
    printf("表是否为空：%d (1:空 0：否)\n",i);

    return 0;
}

posted @ 2012-08-21 16:25 hoshelly 阅读(348) | 评论 (0) | 编辑收藏

图的邻接表表示

#include<stdio.h>
#include<stdlib.h>
typedef struct node *link;
struct node
{ int v; link next; };
link NEW(int v, link next)
{
    link x = (link)malloc(sizeof(node));
    x->v = v; x->next = next;
    return x;
}

int main()
{
    int i,j;
    link adj[7];
    for(i=0;i<7;i++)
        adj[i] = NULL;
    while (scanf("%d%d",&i,&j) == 2)
    {
        adj[j] = NEW(i,adj[j]);
        adj[i] = NEW(j,adj[i]);
    }
    return 0;
}

posted @ 2012-08-19 20:37 hoshelly 阅读(121) | 评论 (0) | 编辑收藏

图的邻接矩阵表示

代码如下：

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,j,adj[7][7];
    for(i=0;i<7;i++)
        for(j=0;j<7;j++)
            adj[i][j] = 0;
    for(i=0;i<7;i++)
        adj[i][i] = 1;
    while(scanf("%d%d",&i,&j) == 2)
    {
        adj[i][j] = 1;
        adj[j][i] = 1;
    }
    for(i=0;i<7;i++)
    {
        for(j=0;j<7;j++)
        {
            printf("%d ",adj[i][j]);
        }
        printf("\n");
    }
    return 0;
}

结果截图：

posted @ 2012-08-19 19:46 hoshelly 阅读(190) | 评论 (0) | 编辑收藏

填充二维数组

编写一程序，用0或1填充一个二维数组，如果i 和j 的最大公因子为1，则设a[i][j]为1；否则设为0。

代码如下：

#include<stdio.h>
#define N 10
int Maxcom(int a, int b)
{
    while(a!=b)
    {
        if(a>b)
            a=a-b;
        else if(b>a)
            b=b-a;
    }
    return a;
}
int main()
{
    int a[N][N];
    int i,j,max;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {
            if(i==1 && j==1)
                a[i][j]=1;
            else if( i>0 && j>0)
            {
                max = Maxcom(i,j);
                if(max == 1)
                    a[i][j]=1;
                else
                    a[i][j]=0;
            }
            else
                a[i][j]=0;
        }
    }
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    printf("\n");

    return 0;
}

posted @ 2012-08-19 16:22 hoshelly 阅读(499) | 评论 (0) | 编辑收藏

括号匹配

数制转换

十进制转二进制（代码）

二进制转十进制（代码）

求两个线性表的集合

归并两个线性表得到新的线性表

线性表基本操作

图的邻接表表示

图的邻接矩阵表示

填充二维数组

日历

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜