学步园

后缀表示法
在后缀表示法中，操作符位于操作数后面。后缀表示法也称 逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。

Syntax  : operand1 operand2 operator
Example : AB+C*DEF+/-

前缀和后缀表示法有三项公共特征：

• 操作数的顺序与等价的中缀表达式中操作数的顺序一致
• 不需要括号
• 操作符的优先级不相关

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

要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。 优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。

Left associativity  : A+B+C = (A+B)+C
Right associativity : A^B^C = A^(B^C)

转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：

1. 初始化一个空堆栈，将结果字符串变量置空。
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

#include "stdafx.h"
#include <stack>
#include <iostream>
using namespace std;

bool prior(char op1,char op2)
{
 bool ret=false;
 switch (op1)
 {
 case '+':
 case '-':
  switch(op2)
  {
  case '+':
  case '-':
  case '*':
  case '/':
   ret= false;break;
  case '#':
  case '(':
   ret = true;break;
  }
  break;
 case '*':
 case '/':
  switch(op2)
  {
  case'#':
  case '+':
  case '-':
  case '(':
   ret= true;break;
  case '*':
  case '/':
   ret= false;break;
  }
  break;
 }
 return ret;
}

int main(int argc, char* argv[])
{

 char s[]="(A+B)*C-D/(E+F)";
 stack<char> operS;//操作符栈
 int i=0;
 operS.push('#');
 while(s[i]!='/0')
 {
  if(s[i]==' ')
  {
   i++;
   continue;
  }
  if(s[i]>='A' && s[i]<'Z' ) //是字母
  {
   cout<<s[i];
  }
  else//不是字母
  {
   switch(s[i])
   {
   case '+':
   case '-':
   case '*':
   case '/':
    if(prior(s[i],operS.top()))//比栈顶优先级高,直接进栈
    {
     operS.push(s[i]);
    }
    else if(operS.top()!='(')        //比栈顶优先级低，先出栈,s[i]进栈
    {
     cout<<operS.top();
     operS.pop();
     operS.push(s[i]);
    }
    break;
   case '(':      //直接进栈
    operS.push(s[i]);
    break;

   case ')':      //匹配栈内的'(',都出栈，并删除'('
    while(operS.top()!='(')
    {
     cout<<operS.top();
     operS.pop();
    }
    operS.pop();
    break;
   case '#':
    break;
   }
  }
  i++;
 }
 while(!operS.empty())
 {

  cout<<operS.top();
  operS.pop();
 }
 return 0;
}