中缀表达式转为前缀表达式
举例
3 输出 3
1 + 1 输出 (+ 1 1)
2 * 5 + 1 输出 (+ 1 (* 2 5))
2 * ( 5 + 1 ) 输出 (* (+ 1 5) 2)
3 * x + ( 9 + y ) / 4 输出 (+ (* 3 x) (/ (+ 9 y) 4))
 
这是我现有的代码：

#include<iostream>
#include<string>
using namespace std;
#define maxSize 100
class Stack{
public:
 Stack() {top = -1 ; };
 bool Push(char a)
 {  
  if(!IsFull())
  c[++top] = a;
  else
  return false;
  return true;
 }
 bool pop(char &a)
 {
  if(!IsEmpty())
  a = c[top--];
  else
  return false;
  return true;
 }
 bool getTop(char &a)
 {
  if(!IsEmpty())
  a = c[top];
  else
  return false;
  return true;
 }
 bool IsEmpty()
 {
  return top == -1 ? true:false ;
 }
 bool IsFull()
 {
  return top == (maxSize-1) ? true:false ;
 }
private:
 char c[maxSize];
 int top;
};

int string_length(string s)
{
 int n;
 for(n=0 ; s[n]!='\0' ; n++); //O(n)
 n--;
 return n;
}
int priority1(char a) //O(1)
{
 if(a == '#')
  return 0;
 if(a == '(')
  return 6;
 if(a == '*' || a == '/')
  return 4;
 if(a == '+' || a == '-')
  return 2;
 if(a == ')')
  return 1;
 return false;
}
int priority2(char a)
{
 if(a == '#')
  return 0;
 if(a == '(')
  return 1;
 if(a == '*' || a == '/')
  return 5;
 if(a == '+' || a == '-')
  return 3;
 if(a == ')')
  return 6;
 return false;
}

char pre_operator(string s, int n)
{
  while(s[n] >= '0' && s[n] <= '9' || s[n] =='.')
  pre_operator(s, --n);
return s[n];
}

int main()
{
  string s;
 char c[100];
 char a,b;
 cout<<"input string "<<endl;
 cin>>s;
 s = "#"+s;
 int m = 0,n;
 n = string_length(s);
 Stack z;
 z.Push('#');
 while(n >= 0 && !z.IsEmpty()) //O(n*n)
  {
  if(isdigit(s[n]))
  {//cout<<"n is "<<n<<endl;
  z.getTop(a);
  if(priority2(pre_operator(s, n)) >= priority1(a)) //O(n)  
  // if the priority2 of operator right before the s[n] is >= top character in stack,
  //we need ')' here  
  {c[m++] = ')';cout<<"c is "<<pre_operator(s, n)<<endl;}
  while(s[n] >= '0' && s[n] <= '9' || s[n] =='.')
  c[m++] = s[n--];
  c[m++] = ' ';
   
  }
  else
  {
  z.getTop(a);
  if(priority1(a) < priority2(s[n]))
  {
  z.Push(s[n--]);
  z.getTop(a);
  }
  else if(priority1(a) > priority2(s[n]))
  z.pop(b) , c[m++] = b;
  else
  {
  z.pop(b);
  if(b == ')')
  n--;
  }
  }
}
 m--;

 cout<<endl<<"prefix string is ";
 for( ; m >=0 ; n++,m--) //O(n)
 if(c[m] == '+' || c[m] == '-' || c[m] == '*' || c[m] == '/')
  cout<<'('<<c[m];
 else
  cout<<c[m];
 cout<<endl;
 return 0;
}


问题是 输出的右括号不正确，输入是2+3*2， 输出是 （+ 2（* 3 2）