// 中缀转前缀
/*
算法
1）求输入串的逆序。
2）检查输入的下一元素。
3）假如是操作数，把它添加到输出串中。
4）假如是闭括号，将它压栈。
5）假如是运算符，则
i)假如栈空，此运算符入栈。
ii)假如栈顶是闭括号，此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。
iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。
6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
7）假如输入还未完毕，跳转到步骤2。
8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
9）求输出串的逆序。

  假设我们要将表达式2*3/(2-1)+5*(4-1)转换成前缀形式：原表达式的逆序是)1-4(*5+)1-2(/3*2
  输出串的逆序为+/*23-21*5-41，所以，最终求得的前缀表达式是+/*23-21*5-41。
*/

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stack>

// 返回优先级
int priority ( char c )
{
 if ( c == '^' ) return 3 ;// 指数操作符号 Exponential operator
 if ( c == '*' || c == '/' || c == '%' )          return 2 ;
 else if ( c == '+' || c == '-' ) return 1 ;
 else return 0 ;
}

// 中缀转前缀infix to prefix
void ConvertToPrefix (char *s, char *t)
{
 char opr;
 using std::stack;
 stack<char> aStack;
 
 while (*s)
 {     
  //去空格换行 Skip white spaces, if any
  if (*s == ' ' || *s == '\t')
  {
   s ++;
   continue ;
  }
  
  if (isdigit(*s) || isalpha(*s)) // 是操作数(数字和字符) Operands
  {
   while (isdigit(*s) || isalpha(*s))
   {
    *t = *s;
    s ++;
    t ++;
   }
  }
  
  if (*s == ')')
  {
   aStack.push(*s);
   s ++;
  }
  
  if (*s == '*' || *s == '+' || *s == '/' || *s == '%' || *s == '-' || *s == '^') // 运算符号
  {
   if (!aStack.empty())
   {
    opr = aStack.top();
    aStack.pop();
    while (priority(opr) >= priority(*s))
    {
     *t = opr; // 优先级低出栈
     t ++;
     opr = aStack.top();
     aStack.pop();
    }
    aStack.push(opr); // 优先级高压栈
    aStack.push(*s);
   }
   else
    aStack.push(*s) ;
   s ++;
  }
  
  if (*s == '(')
  {
   opr = aStack.top();
   aStack.pop();
   while (opr != ')')
   {
    *t = opr;
    t ++;
    opr = aStack.top();
    aStack.pop();
   }
   s ++;
  }
  
  // 如果输入未完毕，则进入再次循环
 }
 
 while (!aStack.empty()) // 栈不空 While stack is not empty
 {
  opr = aStack.top();
  aStack.pop();
  *t = opr ;
  t ++ ;
 }
 
 t++ ;
}

#define MAX 50
void main( )
{
 char input[MAX];
 char output[MAX];
 
 memset(input, 0, sizeof(input));
 memset(output, 0, sizeof(output));

 // 输入表达式字符
 printf("\nEnter an expression in infix form: ") ;
 gets(input) ;

 // 前缀转换，输出前缀字符
 strrev (input); // 求逆序
 ConvertToPrefix (input, output) ;
 strrev (output); // 求逆序
 printf ( "\nThe Prefix expression is: " ) ;
 puts(output);
 printf("\n");
}