posts - 101,  comments - 57,  trackbacks - 0
再做2269
看了数据结构一书，果然有所提升。在讲到堆栈的应用时提到后缀表达式，令我茅塞顿开！

想起poj的2269，正好书上又没有给出代码。于是乎自己写了一遍。虽然还是没有用编译器的思想来得简约明了。但个人认为这种这也算是一种不错的实现方法了。关于“中缀到后缀的部分”是为解题的关键，但是这个地方还是写得比较垃圾，不过思想一致就行，其他的待以后提高了再做改进吧，看官莫笑~

#include "stdio.h"

// DWORD  0 0 0 0  1  1 1 1 1  32bit
//                    Z  D C B A
//        1  ( * - +

#define ADD  0x80000001
#define SUB  0x80000002
#define MUL  0x80000004
#define LBC  0x80000008

#define MAX_SIZE 255

int  queue[MAX_SIZE];
int  queue_pointer = 0;

int  stack[MAX_SIZE];
int  stack_pointer = 0;

void deal_infix(char *pline)
{
    int temp;

    stack_pointer = 0;
    queue_pointer = 0;

    do
    {
        switch(*pline)
        {
        case '{':
            temp = 0;
            break;
        case '}':
            queue[queue_pointer++] = temp;
            break;
        case '+':
            while (stack_pointer && LBC != stack[stack_pointer - 1])
            {
                queue[queue_pointer++] = stack[--stack_pointer];
            }
            stack[stack_pointer++] = ADD;
            break;
        case '-':
            while (stack_pointer && LBC != stack[stack_pointer - 1])
            {
                queue[queue_pointer++] = stack[--stack_pointer];
            }
            stack[stack_pointer++] = SUB;
            break;
        case '*':
            if (stack_pointer && MUL == stack[stack_pointer - 1])
            {
                queue[queue_pointer++] = stack[--stack_pointer];
            }
            stack[stack_pointer++] = MUL;
            break;
        case '(':
            stack[stack_pointer++] = LBC;
            break;
        case ')':
            while (LBC != stack[stack_pointer - 1])
            {
                queue[queue_pointer++] = stack[--stack_pointer];
            }
            --stack_pointer;
            break;
        default:
            temp |= 1 << (*pline - 'A');
            break;
        }
    }while (*(++pline));

    while (stack_pointer)
    {
        queue[queue_pointer++] = stack[--stack_pointer];
    }
}

void deal_postfix()
{
   // 此处已被省略
}

void output()
{
    int i;

    printf("{");
    for (i = 0; i < 'Z' - 'A' + 1; ++i)
    {
        if (stack[0] & 1 << i)
            printf("%c", i + 'A');
    }
    printf("}\n");
}

int main()
{
    char line[MAX_SIZE];

    while (EOF != scanf("%s", line))
    {
        deal_infix(line);                
        deal_postfix();
        output();
    }
    return 0;
}
posted on 2009-09-30 00:52 margin 阅读(109) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年1月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿

随笔档案

文章分类

文章档案

收藏夹

常去的坛子

  • CVC电脑病毒论坛
  • 很多人说我是AV，我告诉他们：别瞧不起人，我们也能创造价值
  • 安全焦点
  • 黑客聚集的地方，一般是好酒最多的地方...
  • 看雪论坛
  • 国内最强的加密解密论坛，成醉其中经常夜不归宿
  • 驱动开发论坛
  • 厌倦了啤的朋友们，来我们来整点白的...痛痛快快的BSOD也好过隔鞋瘙痒！

我的朋友

  • Sen的blog
  • IDE方面资深的受害者...经常为一个变量的定义找不着北的痛苦程序员(深表同情)
  • 老罗的blog
  • 良师益友，千年水牛，引擎猛男，分析怪兽，墨镜酷哥，台球高手....

搜索

  •  

最新评论