腾讯面试，难住我了

帝王在线

本来投简历想做后台的开发，去了之后发现是被做客户端的给看中了，偶是几乎从来不写界面的，两年没玩过对话框了(本来偶也没写过多少带界面的东西)，聊了几句，说说工作经验，没什么问题，问了一下windows多进程通讯的方式，这个我比<windows核心编程>讲的都熟，除了具体哪些函数怎么调我记不住（偶总是用到查），什么管道，消息，事件，socket，文件，注册表，内存文件影射,mutex等等偶全用过，对内存映射文件还正在深入研究，聊了十分钟左右，拿来四道题(具体记不清楚，只是大概):
1.自绘按钮有几种方式，要处理哪些窗口消息
2.LPCSTR,LPWCSTR,BSTR的转换等,
3.处理+-*/()和数字组成的运算表达式，写出数据结构和伪代码
4.运算两个超大整数

第一题，偶不用已经好多年，以前画过，但都是画着玩，反正自己兴趣不在此，直接说不会
第二题，偶用的时候都是翻MSDN，不记得，说没用过.BSTR是真没用过
第三题，第四题，可是我的强项，嘿嘿，可惜，我一个都没写出来
在纸上，我仅仅把我的思路写出来，回答如下：
第三题：数据结构：树，常规写法，代码量比较大。单纯的四则运算可以用简单的递归实现。（ps:我看到题中的“数据结构”便想到了编译器的实现，便想到用树，嘿嘿，走入了误区，他只是想让用递归写出来，但我以为他是让用树实现，递归哪会用什么数据结构可写啊）
第四题：将两个大数的字符串读入，然后把字符串拆成小串组成两个链表，进行两个链表的组合相乘，再处理输出。

结果是，后来让我到机器上写，偶还是写不出，吭哧了两个小时，到五点半了，头疼恶心（最近身体不适），就给他讲我今天有事情，水平距他们要求比较大，一个都没写出来，他说那“改天吧”，嘿嘿，我就灰溜溜的走了，从来没这么灰过。最另偶郁闷的是，偶问他，有人能两个小时没有提前准备写出那个串处理么？他说，可以的，没说要用树实现，用递归写。偶FT。

面试感觉，不是本来我想尝试的岗位，所以去了解之后就不是很在意。腾讯的员工大部分态度是很好的，公司装修的很气派，可以看出来，应该待遇环境都不错。那是谁说的，系分可以拿1XXXX，偶就是去看看是不是真的，结果做了半天题，没看成。

不过我的面试很失败，偶从没有面试做半天题过，汗。

回来后，我真的觉得自己太受打击了，偶当初考高程时，程序能力题可是满分的，各类复杂的算法和数据结构偶没少用。虽然好久没有看过编译器了，但决定一定要用树把运算表达式写出来，并且不借助任何资料。吭哧了4个小时，终于完成一个不完善的版本。
大数的运算和递归方式处理运算表达式明天晚上再写。
我不知道那个面试我的人想到用树实现没，偶的水平，2个小时是打死都写不完的。偶把偶写的程序贴出来，要是谁去面试，可以借鉴一下，嘿嘿。

帝王在线

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
*
*因为程序退出，就释放进程所有内存,作为演示程序,就不释放内存了
*
*
*
*
**/


typedef struct _node
{
        struct _node*  parent;
        struct _node*  left;
        struct _node*  right;
        char           opt;
        char           c1;
        char           c2;
        int            data;
}node;

node* root;

void error_exit();
int  getint(char** p);
void exec_use_callback(char* p); //通过递归方式计算,因为简单,回头再写
void exec_use_tree(char* p);
void tree_insert_char(char p,node** pnode);
void tree_insert_int(int n,node** pnode);
int  tree_result(node* pnode);
void reset_root(node* pnode);

int main(int argc, char* argv[])
{
        char  buf[1024];
        printf("start test program for compute\n");
        if( argc<2)
        {
                printf("arg is error!\n");
                exit(1);
        }

        memset(buf,0,1024);
        if(strlen(argv[1])>1023) {
                printf("cmd is too long ,can't big than 1023\n");
                exit(1);
        }
        strncpy(buf,argv[1],1023);

        printf("the expression is: %s\n",buf);
        exec_use_tree(buf);
        exec_use_callback(buf); //暂未实现

        return 0;
}

void error_exit()
{
        printf("error,exit!........\n") ;
        exit(1);
}

void exec_use_callback(char* p)
{
        char* ptmp;
        ptmp = p;
       
        return ;
}

void exec_use_tree(char* p)
{
        char* ptmp;
        int n;
        node* tmp_node;
        ptmp = p;
        root= NULL;
        tmp_node=root;
        while(*ptmp!=0)
        {
                switch(*ptmp)
                {
                case '+':
                case '-':
                case '*':
                case '/':
                case ')':
                case '(':
                {
                        reset_root(tmp_node);
                        tree_insert_char(*ptmp,&tmp_node);
                        ptmp++;
                }
                break;
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                case '0':
                        {
                                n= getint(&ptmp);
                                if( n<=0) error_exit();
                                reset_root(tmp_node);
                                tree_insert_int(n,&tmp_node);
                        }
                    break;
                default:
                        error_exit();                  
                        break;
                }
        }
        //采用中序遍历二叉树求和
        reset_root(tmp_node);
        n=tree_result(root);
        printf("the result use tree is: %d\n",n);
        return ;
}

void tree_insert_char(char p,node** pnode)
{
        node*  tmp_node;
        node*  tmp_node2;
        switch(p)
        {
        case ')':
                {
                        if(*pnode==NULL) error_exit();
                        tmp_node = (**pnode).parent;
                        while (tmp_node!=NULL)
                        {
                                if(tmp_node->c1=='(') {
                                        *pnode = tmp_node;
                                        tmp_node->c2=')';
                                        if(tmp_node->opt==0)
                                        {
                                                error_exit();
                                        }
                                        return;
                                }
                                tmp_node=tmp_node->parent;
                        }
                        error_exit();
                }
                break;
        case '+':
        case '-':
                {   
                        if( *pnode==NULL){//演示程序,不考虑带符号整数的情况
                                printf("error expression,exit\n");
                                exit(1);
                        }
                        if( (**pnode).parent==NULL)
                        {   //根结点时
                                tmp_node= (node*)malloc(sizeof(node));
                                memset(tmp_node,0,sizeof(node));
                                tmp_node->left = *pnode;
                                (**pnode).parent = tmp_node;
                                *pnode =tmp_node;
                                tmp_node->opt = p;
                        }else{
                                tmp_node = (**pnode).parent;
                                while (tmp_node!=NULL&&tmp_node->opt!=0)
                                {
                                        tmp_node = tmp_node->parent;
                                }
                                if( tmp_node==NULL)
                                {
                                        tmp_node= (node*)malloc(sizeof(node));
                                        memset(tmp_node,0,sizeof(node));
                                        tmp_node->left = root;
                                        root = tmp_node;
                                        *pnode =tmp_node;
                                        tmp_node->opt = p;
                                }else{
                                        tmp_node->opt = p;
                                        *pnode=tmp_node;
                                }
                        }
                }
                break;
        case '(':
                {
                        if( *pnode==NULL){
                                *pnode= (node*)malloc(sizeof(node));
                                memset(*pnode,0,sizeof(node));
                                (**pnode).c1 = p;
                                root = *pnode;
                        }else{
                                tmp_node= (node*)malloc(sizeof(node));
                                memset(tmp_node,0,sizeof(node));
                                tmp_node->parent=*pnode;
                                tmp_node->c1='(';
                                if((**pnode).left==NULL){
                                        (**pnode).left = tmp_node;
                                }else if((**pnode).right==NULL)
                                {
                                        (**pnode).right = tmp_node;
                                }else{
                                        error_exit();
                                }
                                *pnode=tmp_node;
                        }
                }
                break;
        case '*':
        case '/':
                {
                        if( *pnode==NULL){
                                printf("error expression,exit\n");
                                exit(1);
                        }
                        tmp_node= (node*)malloc(sizeof(node));
                        memset(tmp_node,0,sizeof(node));
                        (*tmp_node).opt = p;
                        tmp_node->parent=(**pnode).parent;
                        tmp_node->left = *pnode;
                        if((**pnode).parent!=NULL)
                        {
                                tmp_node2 = (**pnode).parent;
                                if( tmp_node2->left==*pnode)
                                {
                                        tmp_node2->left =tmp_node;
                                }else{
                                        tmp_node2->right = tmp_node;
                                }
                        }
                        (**pnode).parent = tmp_node;
                        *pnode = tmp_node;
                }
                break;
        default:
                {
                        printf("unknow char,exit!\n");
                        exit(1);
                }
        }
        return ;
}

void tree_insert_int(int n,node** pnode)
{
        node*  tmp_node;
        tmp_node= (node*)malloc(sizeof(node));
        memset(tmp_node,0,sizeof(node));
        tmp_node->data = n;
        tmp_node->parent = *pnode;
        if( *pnode==NULL)
        {
                root =tmp_node;
        }else if((**pnode).left==NULL)
        {
                (**pnode).left = tmp_node;
        }else if ((**pnode).right==NULL)
        {
                (**pnode).right = tmp_node;
        }else
        {
                error_exit();
        }
        *pnode = tmp_node;
        return ;
}

int  getint(char** p)
{
        int ret;
        ret=0;
        while((**p)>='0'&&(**p)<='9')
        {
                ret=ret*10+(**p)-'0';
                (*p)++;
        }
        return ret;
}

//递归计算树中数据和
int  tree_result(node* pnode)
{
        int ret;
        ret = 0;
        if(pnode==NULL ) error_exit();
        if( pnode->right==NULL&&pnode->left==NULL) return pnode->data;
        if( pnode->right==NULL|| pnode->left==NULL ) error_exit();
        switch(pnode->opt)
        {
        case '+':
                {
                        return (tree_result(pnode->left)+tree_result(pnode->right));
                }
                break;
        case '-':
                {
                        return (tree_result(pnode->left)-tree_result(pnode->right));
                }
                break;
        case '*':
                {
                        return (tree_result(pnode->left)*tree_result(pnode->right));
                }
            break;
        case '/':
                {
                        return (tree_result(pnode->left)/tree_result(pnode->right));
                }
            break;
        default:
                error_exit();
            break;
        }
        return ret;
}

void reset_root(node* pnode)
{
        root = pnode;
        if( root==NULL ) return;
        while (root->parent!=NULL)
        {
                root = root->parent;
        }
}

/*
按照算法, ((1+2*3)*4+5)*(6+7*(8+9))+10 表达式生成的树形状如下:
--------------------------------------------------------------
                         +
                        /  \
                       /    \
                     *     10
                   /   \
                  /      \
                (+)     (+)
               /  \      / \
              /    \    /   \
             *      5 6    *
            /  \            / \
           /    \          /    \
          (+)  4       7    (+)
         / \                   /  \
        /   \                 /    \
      1    *               8     9
           /  \
          /    \
        2      3
-------------------------------------------------------------------------
按照算法,1+(2+3)*(4+5)*6表达式生成的树如下:
-------------------------------------------------------------------------

                +
                / \
               /   \
             1     *
                  /   \
                 /     \
               (+)     *
               / \      / \
              /   \    /   \
            2     3 (+)   6
                      / \
                     /   \
                   4     5
                       
*/

converse

第三题不需要用到树就可以解决了吧？用栈就可以了，我记得K&R或者是严蔚敏的数据结构里面有类似的题目。

converse

伪代码：
读入一个符号，如果是运算符号，压栈。
如果是一个数字，检查当前栈定元素是不是运算符号，如果是那么把这个符号和上面的一个数字（如果不是数字就报错）取出进行运算，运算完毕之后把前面进行计算用的符号和数字出栈，运算结果入栈。
括号的处理我这里省略，主要是要考虑是否匹配的问题，完全不用树就可以实现这个的。

PS：我相信当初出这个试题的考官只想知道你的思路，不会让你把一个完全正确的代码写出来的，换了是他，也许写一次就能完全无错误也是很难的。

mq110

生成表达式树的算法也不错。

mq110

运行了一下你写的程序，达不到你说的效果.

mingyanguo

第三个不必用树吧。单纯的计算递归就好了。编译器生成树是为了方便进一步的处理。

converse

其实就是最简单的状态机而已,你把它给想的复杂了

freet15

楼主想复杂了，不过也是经验啊，写代码嘛，kiss原则(keep it simple and stupid)

帝王在线

是啊，我给想复杂了，我看他要求写出数据结构，以为他要考察的是复杂的数据结构，就想到树了，我在答题纸上写的是:这个东西用递归就可以完成，比较简单，用树是标准写法。

所以偶很失败。

这些题是到环境上编写的，我在纸上写出了思路，但要求在计算机上实现啊，我走的时候还问我，调通了没：）
我是回来后还花了4个小时才用树实现的，今天晚上看看用递归要多久.