中缀到后缀表达式的转换

更多精彩请到 http://www.139ya.com

转自: 中缀到后缀表达式的转换

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   postfix.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-6 16:00:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

// 算法：
// 1)检查输入的下一元素。
// 2)假如是个操作数，输出。
// 3)假如是个开括号，将其压栈。
// 4)假如是个运算符，则
//   i) 假如栈为空，将此运算符压栈。
//   ii) 假如栈顶是开括号，将此运算符压栈。
//   iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。
//   iv) 否则栈顶运算符出栈并输出，重复步骤4。
// 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。
// 6)假如输入还未完毕，跳转到步骤1。
// 7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。

#include <stdio.h>
#include "stack.h"

// 返回操作符的优先级
// +和-的优先级是一样的，*和/的优先级也是一样的，但+和-的优先级要比*和/的低。
static int GetPRI(const char optr)
{
   switch (optr)
   {
   case '+': return 1;
   case '-': return 1;
   case '*': return 2;
   case '/': return 2;
   default : return 0;
   }
}

// 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比，
// 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。
static void ProcessStackPRI(
   CStack<char> &stack,
   const char optr,
   char **szPostfix
)
{
   ASSERT(*szPostfix);

   int i;
   int nRetCode;
   char chStackOptr;
   int nCount = stack.GetCount();

   for (i = 0; i <= nCount; ++i)
   {
       nRetCode = stack.top(&chStackOptr);
       if (
           (0 == nRetCode) ||                  // 栈顶为空，新操作符添加到栈顶
           (GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低
       )
       {
           stack.push(optr);
           break;
       }
       else
       {
           // 如果栈顶操作符优先级不低于当前的，则栈顶元素出栈并输出：
           stack.pop();
           *(*szPostfix)++ = chStackOptr;
       }
   }
}

static void Infix2Postfix(
   const char *szInfix,
   char *szPostfix
)
{
   ASSERT(szPostfix);

   char chOptr;
   int nRetCode;
   CStack<char> stack;

   while (*szInfix)
   {
       switch (*szInfix)
       {
       // 忽略空格和TAB：
       case ' ':
       case '\t':
           break;

       // 对操作符进行优先级判断，以便决定是入栈还是输出：
       case '+':
       case '-':
       case '*':
       case '/':
           nRetCode = stack.IsEmpty();
           if (!nRetCode)
               ProcessStackPRI(stack, *szInfix, &szPostfix);
           else
               stack.push(*szInfix);   // 当栈为空时，毫无疑问操作符应该入栈
           break;

       // 遇到左括号时，无条件入栈，因为它的优先级是最高的
       case '(':
           stack.push(*szInfix);
           break;

       // 遇到右括号时，逐个把栈中的操作符出栈，直到遇到左括号为止
       case ')':
           do
           {
               nRetCode = stack.pop(&chOptr);
               if (nRetCode && ('(' != chOptr))            // 左括号本身不输出
                   *szPostfix++ = chOptr;
           } while (!stack.IsEmpty() && ('(' != chOptr));  // 遇到左括号为止
           break;

       // 其余的情况，直接输出即可
       default:
           *szPostfix++ = *szInfix;
           break;
       }
       ++szInfix;
   }
   // 如果输入的内容已经分析完毕，那么就把栈中剩余的操作符全部出栈
   while (!stack.IsEmpty())
   {
       nRetCode = stack.pop(&chOptr);
       *szPostfix++ = chOptr;
   }
   *szPostfix = '\0';
}

int main()
{
   char *szInfix = "a+b*c+(d*e+f)*g";
   char szPostfix[255];

#ifdef _DEBUG
   _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

   Infix2Postfix(szInfix, szPostfix);

   printf("Infix   : %s\n", szInfix);
   printf("Postfix : %s\n", szPostfix);
}