Happy every day~

hdoj_1468解题报告

 

#include"iostream"
#include"string.h"
using namespace std;
//------------------------------表达式单元-----------------------
//---------------------------------------------------------------
struct node {
    int coe;//coefficient系数
    int fre;//frequency次数
    struct node *next;
};
//-------------------------------表达式----------------------------
//------------------------------------------------------------------
struct exp{//expression 链表实现——无表头
    struct node *head;
    int coe;
    int fre;//循环为N次的时候，coe=0,fre=1;为k次的时候，coe=k,fre=0;
    struct exp* plus(exp *a);
    void insert( struct node *x);
    void show();
};
struct exp * exp::plus(exp *a){
    struct node *p,*q,*t;
    struct node h;
    p=head;
    q=a->head;
    t=&h;
    while(p && q){
        if(p->fre > q->fre ){
            t-> next=p;
            t = t->next;
            p = p->next;
        }
        else if(q->fre > p->fre ){
            t-> next = q;
            t = t-> next;
            q = q-> next;
        }
        else {
            p-> coe += q-> coe;//系数全为正
            t-> next = p;
            t = t-> next;
            p = p-> next;
            q = q-> next;
        }
    }
    if(p)    t-> next = p;
    else    t->next = q;
    head = h.next;
    return this;
}
void exp::insert(struct node *x){
    struct node h,*p;
    h.next = head;
    p = &h;
    while(p->next && p->next->fre > x->fre){
        p = p->next;
    }
    if(p-> next){
        if(p->next->fre == x->fre){
            p->next->coe +=x->coe;
        }
        else{
            x->next = p->next->next;
            p->next = x;
        }
    }
    else{
        p->next=x;
    }
    head = h.next;
}
void exp::show(){
    //--------------------输出函数细节--------------------
    //(1)当为空链表是，表示时间为0
    //(2)系数为0的节点不要输出,全为0则表示总时间为0
    struct node *p;
    p = head;
    printf("Runtime = ");
    bool temp=0;
    while(p){
        if(p->coe==0){
            p = p->next;
            continue;
        }
        temp=1;
        if(p->fre==0){
            printf("%d",p->coe);
        }
        else{
            if(p->coe > 1){
                printf("%d",p->coe);
                if(p->fre != 0)
                    printf("*");
            }
            if(p->fre != 0)
                printf("n");
            if(p->fre > 1)
                printf("^%d",p->fre);
        }
        if(p->next)
            printf("+");
            
        p = p->next;
    }
    if(!temp)
        printf("0");
    printf("\n\n");
}
//------------------------------操作符栈----------------------
//------------------------------------------------------------
struct operation_stack{//operation stack
    char op[1000];
    int top,base;
    //    struct node *p;
    void push(char x);
    char pop();
};
void operation_stack::push(char x){
    op[ top++ ] =x;
}
char operation_stack::pop(){
    return op[ --top];
}
//-----------------------------操作数栈----------------------
//-------------------------------------------------------------
struct operand_stack{//operand stack
    struct exp * ra[1000];
    int top,base;
    void push(struct exp * x);
    struct exp *pop();
};
void operand_stack::push(struct exp *x){
    ra[ top++ ] = x;
}
struct exp *operand_stack::pop(){
    return ra[ --top];
}
//-----------------------------主函数--------------------------
//--------------------------------------------------------------
/*
讲每个代码换成运算式来作
数据处理举例
对于SAMPLE
我处理成#0+(<n> 0+4+(<3> 0+(<n> 0+1)+2)+1)+17#
左小括号后的中括号代表LOOP后的参数，最后用乘处理这个数
遇到')'也就是"END"就对前面的式子做一次处理计算出这个括号内的表达式值化成一个结果链表
*/
operation_stack    op;//操作符栈
operand_stack    ra;//值链表栈
int a[1000],len;//LOOP值数组
int main()
{
    int t,i,j,l=1;
    char o[10],order;
    struct node *p1;
    struct exp *p2,*p3;
    scanf("%d",&t);
    while(t--){
        op.top = op.base = 0;
        ra.top = ra.base = 0;
        len=0;
        while(scanf("%s",&o),strcmp(o,"BEGIN")) ;
        op.push('#');
        p2 = (struct exp *)malloc(sizeof(struct exp));
        p2->head=NULL;
        ra.push(p2);
        while(1){
            while(scanf("%s",&o),o[0]==0 || o[0]==32);
            //---------------CASE 1:------------------------
            if(strcmp(o,"LOOP")==0){
                scanf("%s",o);
                if(o[0]=='n')
                    a[len++]=-1;
                else{
                    j=0;
                    for(i=0;i<strlen(o);i++)
                        j=j*10+o[i]-'0';
                    a[len++]=j;
                }
                op.push('+');
                op.push('(');
                p2 = (struct exp *)malloc(sizeof(struct exp));
                p2->head=NULL;
                ra.push(p2);
            }
            //--------------CASE 2:---------------------------
            else if(strcmp(o,"OP")==0){
                scanf("%d",&i);
                p1 = (struct node *)malloc(sizeof(struct node));
                p2 = (struct exp *)malloc(sizeof(struct exp));
                p1->coe=i;    p1->fre=0;    p1->next = NULL;
                p2->head=p1;
                ra.push(p2);
                op.push('+');
            }
            //--------------CASE 3:----------------------
            else if(strcmp(o,"END")==0){
                while(1){
                    order = op.pop();
                    if(order == '#' || order == '(')    break;
                    p2 = ra.pop();
                    p3 = ra.pop();
                    p2->plus(p3);
                    ra.push(p2);
                }
                if(order=='('){
                    p2 = ra.pop();
                    if(!p2->head){
                        p2->head=(struct node *)malloc(sizeof(struct node));
                        p2->head->coe=1;
                        p2->head->fre=0;
                        p2->head->next=NULL;
                    }
                    p1 = p2->head;
                        
                    i=a[--len];
                    if(i>=0){
                        while(p1){
                            p1->coe*=i;
                            p1 = p1->next;
                        }
                    }
                    else{
                        while(p1){
                            p1->fre++;
                            p1 = p1->next;
                        }
                    }
                    ra.push(p2);
                    
                }
                if(order == '#'){
                    printf("Program #%d\n",l++);
                    p2=ra.pop();
                    p2->show();
                    break;
                }
            }
        }
    }
    return 0;
}












posted on 2009-04-14 21:42 April4 阅读(141) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理