有位朋友去面试,对方给了一道面试题目,将中缀表达式转化为后缀表达式。要求按照给定方法实现代码编程,并且做一些基本的验证。时间给的比较充分——一个上午。结果参加面试12个人,半个小时候后就有8个放弃,有两个人按时提交代码并且基本通过。回来后告诉我,我非常有兴趣,所以自己也写了一下。代码只能做基本的测试,没有使用价值。但是基本思想使用到了。

     首先:我们看看对方提供的资料。

1+((2+3)×4)-5

(1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;

(2) 从左至右扫描中缀表达式;

(3) 遇到操作数时,将其压入S2;

(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:

(4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

(4-2) 比栈顶高,也将运算符压入S1         (注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);

(4-3) 比栈顶低或相同,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;

(5) 遇到括号时:

(5-1) 如果是左括号“(”,则直接压入S1;

(5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;

 (6) 重复步骤(2)至(5),直到表达式的最右边;

 (7) 将S1中剩余的运算符依次弹出并压入S2;

 (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

 

tupian.jpg

      可以看出对方提供的资料已经非常充分了。不但提供例子,还提供了方法。因为是现场写代码我们就按照对方提供思路开始。首先必须设计栈的数据结构。因为使用的C语言,没有内置的栈类,所以我们必须自己写栈的数据结构和操作方法。这个非常基本。

#define   STACK_MAX      64
#define   BOTTOM_NUMBER  -1
 
typedef struct{
   int       TOP;
   const  int BOTTOM;
   char        STACK_M[STACK_MAX];
}STACK_BASE_TY;

   我们采用数组STACK_M作为栈的实体,BOTTOM作为栈底,使用数组作为栈的实体,那么就可以规定栈底的索引值为“-1”。栈从0~STACK_MAX-1正向增长。当然我们还要编写栈的操作方法,为了方便管理我们编写一个结构体来管理函数。

typedef struct {

 
   void (*Initial) ( STACK_BASE_TY *pStack);
   int (*Push) ( STACK_BASE_TY *pStack, int data);
   int (*Pop) ( STACK_BASE_TY *pStack,char *pdata);
   char (*GetTopData)( STACK_BASE_TY *pStack);
   int (*GetTopLocate)( STACK_BASE_TY *pStack);
 
}STACK_OPTION_TY;
 
 
  我们规划一下每个函数的功能。
  void (*Initial) ( STACK_BASE_TY *pStack);是初始化栈,初始化一个栈的目的是建立一个空栈。建立一个空栈就是将TOP指针指向BOTTOM。pStack指向要初始化的栈的实体。
 
   int (*Push) ( STACK_BASE_TY *pStack, int data)是压栈,将一个数据的值压入栈顶。返回0,栈满,压入错误;返回1,压栈成功。
 
   int (*Pop) ( STACK_BASE_TY *pStack,char *pdata)出栈,弹出栈顶的数据。*pdata接收出栈数据的值。返回0,栈空,出栈错误;返回1,出栈成功。
   
    char (*GetTopData)( STACK_BASE_TY *pStack);获取栈顶数据值,但是栈顶指针不发生变化。
 
    int (*GetTopLocate)( STACK_BASE_TY *pStack);获取栈顶的位置。
 
 
void initialStack(  STACK_BASE_TY *pStack )
{
    int i;
    pStack->TOP = -1;
 
    for( i =0; i< STACK_MAX; i++ ) pStack->STACK_M[i]=0;
}
 
 
int pushStack(  STACK_BASE_TY *pStack, int data )
{
    pStack->TOP++;
 
   if( pStack->TOP>=STACK_MAX )
   {
      pStack->TOP--;
      return 0;
   }
   else
   {
     pStack->STACK_M[ pStack->TOP] = data;
     return 1;
   }
}
 
 
int popStack(  STACK_BASE_TY *pStack, char *pdata )
{
   if(pStack->TOP<=pStack->BOTTOM)
   {
      return 0;
   }
   else
   {
       *pdata = pStack->STACK_M[pStack->TOP];
       pStack->TOP--;
       return 1;
   }
 
}
 
 
int  getStackTopLocate(STACK_BASE_TY *pStack)
{
   
    return pStack->TOP;
}
 
char  getTopData(  STACK_BASE_TY *pStack )
{
     return pStack->STACK_M[pStack->TOP];
}
 
 
定义两个栈,
STACK_BASE_TY    statck_option={0,-1,{0,0}};
STACK_BASE_TY    statck_result={0,-1,{0,0}};
 
STACK_BASE_TY*  const pOptionStatck = &statck_option;
STACK_BASE_TY*  const pResultStatck = &statck_result;
 
 
   statck_option存放运算符号,statck_result存放最终结果。
 
STACK_OPTION_TY  stackOption =                              
 
                         {initialStack,pushStack,popStack,getTopData,getStackTopLocate} ; 
 
定义一个函数结构体,并且初始化,使得我们可以方便的调用栈的操作方法。
 
const char str[] ="(1+2+3)*(4+5)";  测试公式
 
int main(  )
{
    unsigned  int i;
    char temp;
    char opCh_0,opCh_1;
    int compPr;
 
    stackOption.Initial(pOptionStatck);
    stackOption.Initial(pResultStatck);
 
 
    for( i=0;  i<strlen(str); i++)
    {
        switch( str[i])
        {
             case '0':
             case '1':
             case '2':
             case '3':
             case '4':
             case '5':
             case '6':
             case '7':
             case '8':
             case '9':
                   stackOption.Push(pResultStatck,str[i]);
                  break;
             case '+':
             case '-':
                  if( stackOption.GetTopLocate(pOptionStatck) ==-1 )
                  {
                      stackOption.Push(pOptionStatck,str[i]);
                  }
                  else
                 {
                     opCh_0 =  stackOption.GetTopData(pOptionStatck);
                     if( opCh_0=='(')
                     {
                         stackOption.Push(pOptionStatck,str[i]);
                      }
                      else
                     {
      
                         while((stackOption.GetTopLocate(pOptionStatck) !=-1 )&&
 
                            (opCh_0!='('))
                        {
                               if(stackOption.Pop(pOptionStatck,&opCh_0 )!=0)
                              {
                                  if(opCh_0!='(')
                                  {
                                      stackOption.Push(pResultStatck, opCh_0); 
                                   }
  
                               }
 
                           }
 
                             stackOption.Push(pOptionStatck,str[i] );
                      }
 
 
                    }
                    break;
             case '*':  
             case '/':
                  if( stackOption.GetTopLocate(pOptionStatck) ==-1 )
                  {
                      stackOption.Push(pOptionStatck,str[i]);
                  }
                  else
                  {
                       opCh_0 =  stackOption.GetTopData(pOptionStatck);  
                       if(( opCh_0=='(')||(opCh_0=='+')||(opCh_0=='-'))
                       {
                           stackOption.Push(pOptionStatck,str[i]);
                        }
                       else
                        {
    
                          while((stackOption.GetTopLocate(pOptionStatck) !=-1 )&&
                            (opCh_0!='('))
                           {
                               opCh_0 =  stackOption.GetTopData(pOptionStatck); 
 
                               if(( opCh_0=='(')||(opCh_0=='+')||(opCh_0=='-'))
                               {
 
                                    break;
                                }
                                else
                                {
                                        stackOption.Pop(pOptionStatck,&opCh_0);
                                         stackOption.Push(pResultStatck,opCh_0);
 
                                 }
                            }
 
                                stackOption.Push(pOptionStatck,str[i] );
 
                            }
 
                        }
 
                       break;
                case '(':
   
                         stackOption.Push(pOptionStatck,str[i]);
 
                         break;
                case ')':
                        if( stackOption.GetTopLocate(pOptionStatck) ==-1 )
                       {
   
                        }
                        else
                        {  
                           opCh_0 =  stackOption.GetTopData(pOptionStatck);  
                           if( opCh_0=='(')
                           {
                              stackOption.Pop(pOptionStatck,&opCh_0);
  
                            }
                            else
                            {
                                while((stackOption.GetTopLocate(pOptionStatck) !=-1 )&&
 
                                (opCh_0!='('))
                                {
                                     opCh_0 =  stackOption.GetTopData(pOptionStatck); 
                                     if( opCh_0!='(')
                                     {
                                         stackOption.Pop(pOptionStatck,&opCh_0);
                                         stackOption.Push(pResultStatck,opCh_0);
                                      }
                                     else
                                     {
                                         stackOption.Pop(pOptionStatck,&opCh_0);
                                      }
  
                                   }
                                }
 
                            }
                         break;
                default:
                          break;
             }
 
 
 
 
}
 while(stackOption.Pop(pOptionStatck,&opCh_0)!=0)
 {
     stackOption.Push(pResultStatck,opCh_0);
 
 }
 
 while(stackOption.Pop(pResultStatck,&opCh_0)!=0)
{
    printf("%c,",opCh_0);
}
 
    printf("\n");
 
    return 0;
}

在程序中我们设置了一个字符串const char str[] ="(1+2+3)*(4+5)"; 作为测试目标。

然后我们看看输出结果:

1111111.JPG

     因为我们是从栈中输出的,所以倒着看就是完全正确。我大概使用了半个小时完成了以上代码,所以这个问题其实还是比价容易解决的。