栈的应用-表达式转换

中缀->后缀

先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。

中缀->前缀

先对中缀表达式按运算优先次序通统加上括号，再把操作符前移到左括号前并以就近移动为原则，最后将所有括号消去。

代码实现中缀转为后缀

原理：

• isp叫做栈内(in stack priority)优先数
• icp叫做栈外(in coming priority)优先数。
• icp>isp则入栈；icp<isp则出栈、输出；icp=isp只出栈 (的栈外优先级最高，一来即入栈；入栈后优先级极低，这样其他操作符可以入栈。
• 其他操作符进入栈后优先级升1，这样可以保证相同优先级的从左到右计算。
• 优先级相同:( ) # #

算法：

1. 操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。
2. 重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’，停止循环。

循环过程：

1. 若ch是操作数直接输出，读入下一个字符ch。
2. 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：
   • 若 icp(ch) > isp(op)，ch入栈，读入下一个字符ch。
   • 若 icp(ch) < isp(op)，出栈、输出,ch继续比较。
   • 若 icp(ch) == isp(op)，出栈、不输出，读入下一个字符ch。
3. 算法结束，输出序列即为所需的后缀表达式。
   代码实现：

   #include <iostream>
   
   using namespace std;
   class steak;
   class StackNode
   {
       friend class LinkedStack;
   
   public:
       StackNode *link;
       char data;
   
   public:
       StackNode(StackNode *ptr = NULL)
       {
           link = ptr;
       }
       StackNode(char &c, StackNode *ptr = NULL)
       {
           data = c;
           link = ptr;
       }
   };
   class LinkedStack
   { //链式栈类定义
   public:
       StackNode *top; //栈顶指针
   public:
       LinkedStack(); //构造函数
       void getTop(char &ch);
       void Push(char &ch); //进栈
       int Pop(char &ch);   //退栈
       void makeEmpty();    //清空栈的内容
       int IsEmpty() { return (top == NULL) ? 1 : 0; }
   };
   LinkedStack::LinkedStack()
   {
       top = NULL;
   }
   void LinkedStack::getTop(char &ch)
   {
       ch = top->data;
   }
   void LinkedStack::makeEmpty()
   {
       if (top != NULL)
       {
           StackNode *p = top->link;
           while (top != NULL)
           { //逐个结点释放
               p = top;
               top = top->link;
               delete p;
           }
       }
   }
   void LinkedStack::Push(char &ch)
   {
       top = new StackNode(ch, top); //创建新结点
   }
   
   int LinkedStack::Pop(char &ch)
   {
       //删除栈顶结点, 返回被删栈顶元素的值。
       if (IsEmpty())
           return 0;       //栈空返回
       StackNode *p = top; //暂存栈顶元素
       top = top->link;    //退栈顶指针
       ch = p->data;
       delete p; //释放结点
       return 1;
   }
   int isp(char &c)
   {
       //返回栈内优先级
       if (c == '#')
       {
           return 0;
       }
       else if (c == '(')
       {
           return 1;
       }
       else if (c == ')')
       {
           return 6;
       }
       else if (c == '+'  c == '-')
       {
           return 3;
       }
       else
       {
           return 5;
       }
   }
   int icp(char &c)
   {
       //返回栈外优先级
       if (c == '#')
       {
           return 0;
       }
       else if (c == '(')
       {
           return 6;
       }
       else if (c == ')')
       {
           return 1;
       }
       else if (c == '+'  c == '-')
       {
           return 2;
       }
       else
       {
           return 4;
       }
   }
   void postfix() //把中缀表达式e转换成后缀表示并输出
   {
       LinkedStack S;
       char ch = '#', ch1, op;
       S.Push(ch);
       cin.get(ch);
       while (!S.IsEmpty())
       {
           if (isdigit(ch))
           {
               cout << ch;
               cin.get(ch);
           }
           else
           {
               S.getTop(ch1);
               if (icp(ch) > isp(ch1))
               {
                   S.Push(ch);
                   cin.get(ch);
               }
               else if (icp(ch) < isp(ch1))
               {
                   S.Pop(op);
                   cout << op;
               }
               else
               {
                   S.Pop(op);
                   if (op == '(')
                       cin.get(ch); //相等，此时ch为’)’ ，op=‘(‘ 或者#(准备结束)；
               }
           }
       }
   }
   int main()
   {
       postfix();
       return 0;
   }