逆波兰式.cpp

逆波兰式 VC开发环境 希望大家多多支持哈 谢谢了啊 谢谢

#include<iostream>
#include<cstdlib>
#define STACK_INIT_SIZE 10;
//#define STACKINCREMENT 10;
using namespace std;
 
typedef struct { //构造栈 
       char* top;
       char* base;
       int  stacksize;
       }Stack; 
       
int JudegPri(char c,Stack s,char a[7],char b[7][7]); //优先级判断函数 
bool JudgeOperate(char c,char a[7]);  //运算符判断函数  

bool InitStack(Stack &s) //栈的初始化 
 {
  s.base=(char*)malloc(15*sizeof(char));//初始空间分配 
  if(!s.base) return 0;
  s.top=s.base;
  s.stacksize=STACK_INIT_SIZE;//栈大小初始化 
  return 1;          
 }
 
char push(Stack &s,char e)//压栈 
{   
  *s.top++=e;  
} 

char pop(Stack &s,char e)//出栈 
{
   e=*--s.top;
}

char GetTop(Stack s,char e)//获取栈顶元素 
{
 if(s.top==s.base)  return 0;  
 e=*(s.top-1);
 return e;
}  

int main()  //主函数 
{
  Stack s;// 构造栈Stack的对象 s
  InitStack(s);//调用栈初始化函数 
  bool flag=1; //栈为空的标志,1表示非空    
  bool sign=1;
  int  label =0;
  char c;//当前元素 
  char e;//栈顶元素 
  char a[7]={'+','-','*','/','#','(',')'};//用#替代↑ 
  char b[7][7]={ {'=','=','<','<','<','>','>'},  //运算符优先级关系矩阵 
                  {'=','=','<','<','<','<','>'},
                  {'>','>','=','=','<','<','>'},
                  {'>','>','=','=','<','<','>'},
                  {'>','>','>','>','=','<','>'},
                  {'<','<','<','<','<','=','='},
                  {'<','<','<','<','<',' ','='}
                };
loop:
 cout<<"请输入中缀运算表达式,以$结尾"<<endl;
  while(flag)
 { sign=1;
   cin>>c;  //输入一个字符 
   if(c=='$') //字符等于$时，表示输入串为空 
   { while(s.top!=s.base) //栈不空 
        {  
             cout<<pop(s,e)<<" ";  //退栈输出 
        }
     flag=0; //栈为空的标志   
   } //  if(c==' ') 
   
   else if(!JudgeOperate(c,a))//(c!=' ')//如果是运算符 
      { if(c=='(')
           { label++;
             push(s,c);
           }
       else if(s.top!=s.base)  //栈不空 
        {
          if(JudegPri(c,s,a,b))//是运算符 、栈也不空，判断输入符号优先级高于当前栈顶符号优先级 
              push(s,c);
          else  //判断输入符号优先级是否高于当前栈顶符号优先级 
             if(c==')') //输入符号是')' 
             { label--;
               while(sign)
               { 
                 if(GetTop(s,e)=='(')   //栈顶符号是'('
                      {
                        pop(s,e);  //退栈
                        sign=0; //
                      }
                 else 
                   { if(s.top==s.base) //栈空  
                       {    
                        cout<<"error!";
                        sign=0;
                        flag==0;
                       } 
                      else  cout<<pop(s,e)<<" ";//退栈输出 
                   } 
               }//while(sign)
             }// if(c==')') 输入符号是“)”    
           
          else {
                cout<<pop(s,e);//退栈输出 ,应该继续判断栈是否为空
                //及优先级，如果不空，优先级不高就出栈 ，否则进栈 
                while(s.top!=s.base&&(!JudegPri(c,s,a,b)))
                    cout<<pop(s,e)<<" ";
                push(s,c);
               }                                 
        } //  if(s.top!=s.base)  //栈不空  
       
    else  push(s,c);    //栈空 ,运算符进栈                            
   } //if(JudgeOperate(c,a))

   else cout<<c<<" ";//如果不是运算符，直接输出 
  }
  cout<<endl;
  if(label!=0)  {cout<<"Input Error ! Try Again! "<<endl;
                  label=0;
                  flag=1;
                  goto loop;
                  
                }
  system("pause");
}


int JudegPri(char c,Stack s,char a[7],char b[7][7])//判断优先级，若当前优先级高返回1 ，否则返回0 
{   
    char e;
    int k,d;
    for(int i=0;i<7;i++)
      {
      if(a[i]==c)   //当前运算符 
         k=i;
      if(a[i]==GetTop(s,e)) //栈顶运算符 
        d=i;  
       }
    if(b[k][d]=='>')//若当前运算符优先级高，返回1 
         return 1;   
      else return 0;//否则，返回0 
}

 bool JudgeOperate(char c,char a[7])//判断是不是运算符 ，是返回0，否则返回1
{ bool signal=1;
  for(int j=0;j<7;j++)  
    if(c==a[j])    //是运算符时，标记 signal=0
        signal=0;  
    return signal;  //否则，标记 signal=1         
 }