回 帖 发 新 帖 刷新版面

主题:[原创]栈的应用,表达式求值,可以处理有负数的整型表达式

    

         //     此程序可以处理有负数的整型表达式,望大家多多支持,也希望大家给出批评和建议

#include<iostream>
using namespace std;

typedef struct SqStack{
 int * base;
 int * top;
 int size;
}SqStack;

#define STACK_INIT_SIZE  100
#define STACKINCREMENT   20

 

void InitSqStack(SqStack &t);
void push(SqStack &t, int n);
int out(SqStack &t);
int Empty( SqStack &t);
char GetTop(SqStack &t);
char Precede(char ,char);

int main(){
    char ch;
 SqStack OPTR;InitSqStack(OPTR);
 SqStack OPND;InitSqStack(OPND);
    push(OPTR,'=');
   
 
 ch=getchar();

 if(ch=='-'){         //第一个数为负数
  int m=0;
  ch=getchar();
   while(ch<='9'&&ch>='0'){
    m=m*10+ch-48;
    ch=getchar();                          
       }
    push(OPND,m*(-1));
 }
  
 
 
 while(ch!=10){
  int m=0; int flag=1;   char ch1=ch;

        if(ch1=='('){  
   char ch2;
   push(OPTR,ch);
   while((ch=getchar())=='(')
                 push(OPTR,ch);
   
   ch2=ch;
   if(ch2=='-'){                //出现负数
    flag=-1;
    ch=getchar();
    }
      
  while(ch<='9'&&ch>='0'){
      m=m*10+ch-48;
      ch=getchar();                          
         }
  
      
  if(ch==')')               //形如(-1)的负数 还有形如(-1+2*5  中的负数
     {
     out(OPTR);
     ch=getchar();
     }
 }

 else {
     while(ch<='9'&&ch>='0'){
    m=m*10+ch-48;
    ch=getchar();                          
     }
 }

  if(m)
    push(OPND,m*flag);

  switch(Precede(GetTop(OPTR),ch)){
                
        case '<':push(OPTR,ch);ch=getchar();break;
        
        case '=':out(OPTR);ch=getchar();break;
         
        case '>':{
                     int m2=out(OPND),m1=out(OPND); //注意m1和m2的顺序  后一个操作数先出来用m2接收
                     switch(out(OPTR))
                     {
                          case '+':push(OPND,m1+m2);break;
                                   case '-':push(OPND,m1-m2);break;
                                   case '*':push(OPND,m1*m2);break;
                                   case '/':push(OPND,m1/m2);break;
                      }
      
             break;
      
     }
    }
 }
 printf("%d",out(OPND));
 
 
 getchar();

 
}

 

void push(SqStack &t, int n){              
 if((t.top-t.base)>=t.size){
  t.base=(int *)realloc(t.base,(t.size+STACKINCREMENT)*sizeof(int));
  if(!t.base)
   exit(1);
 }
  *(t.top)=n;
     t.top++;
 
}         

int out(SqStack &t){            
 t.top--;
 return *(t.top);
}           

int Empty( SqStack &t){
 int m=(t.top-t.base); 
 return m;
}   

char GetTop(SqStack &t){
   return *(t.top-1);
}      

char Precede(char c,char d)
{
    char youxian[7][7]=
    {
        {'>','>','<','<','<','>','>'},
        {'>','>','<','<','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'>','>','>','>','<','>','>'},
        {'<','<','<','<','<','=','>'},
        {'>','>','>','>','>','>','>'},
        {'<','<','<','<','<','>','='}
    };
    char opt[7]={'+','-','*','/','(',')','='};
    int m,n,i;
    for(i=0;i<7;i++)
    {
        if(c==opt[i])
        {
            m=i;
        }
        if(d==opt[i])
        {
            n=i;
        }
    }
 return youxian[m][n];
}

void InitSqStack(SqStack &t){
 t.base=(int *)(malloc(sizeof(int)*STACK_INIT_SIZE));
 if(!t.base)
   exit(1);
 t.top=t.base;
 t.size=STACK_INIT_SIZE;
}  


 

0

回复列表 (共1个回复)

沙发

学习了啊~~~

我来回复

您尚未登录,请登录后再回复。点此登录或注册