第六週項目五~~~接尾辞式

/*     
 *Copyright(c)2015,         
 *All right reserved.
 *    ：     .cpp
 *  ：  
 *    ；2015 10 9 
 *   ；v1.0
 *
 *    ：　  sqstack.h       ，                        。
   ，  (56-20)/(4+2)，       ：:56#20#-4#2#+/       #。




 *    ：   
 *    ：     
*/


#include <stdio.h>
#include "sqstack.h"
#include <stdlib.h>


int main()
{
    char exp[]="(56-20)/(4+2)"; //  exp      
    char postexp[200];
    trans(exp,postexp);
    printf("     :%s
",exp);
    printf("     :%s
",postexp);
    return 0;
}


//sqstack.cpp
#include <stdio.h>
#include <malloc.h>
#include "sqstack.h"
int leftpri(char op)    //     op    
{
    int i;
    for (i=0; i<MaxOp; i++)
        if (lpri[i].ch==op)
            return lpri[i].pri;
}

int rightpri(char op)  //     op    
{
    int i;
    for (i=0; i<MaxOp; i++)
        if (rpri[i].ch==op)
            return rpri[i].pri;
}

bool InOp(char ch)       //  ch      
{
    if (ch=='(' || ch==')' || ch=='+' || ch=='-'
            || ch=='*' || ch=='/')
        return true;
    else
        return false;
}

int Precede(char op1,char op2)  //op1 op2           
{
    if (leftpri(op1)==rightpri(op2))
        return 0;
    else if (leftpri(op1)<rightpri(op2))
        return -1;
    else
        return 1;
}
void trans(char *exp,char postexp[])
//      exp        postexp
{
    SqStack *opstack;               //      
    int i=0;                //i  postexp   
    ElemType ch;
    InitStack(opstack);   //             ，    
    Push(opstack, '=');
    while (*exp!='\0')      //exp          
    {
        if (!InOp(*exp))        //        
        {
            while (*exp>='0' && *exp<='9') //     
            {
                postexp[i++]=*exp;
                exp++;
            }
            postexp[i++]='#';   // #         
        }
        else    //       
        {
            GetTop(opstack, ch);   //        
            switch(Precede(ch ,*exp))
            {
            case -1:           //          :  
                Push(opstack, *exp);
                exp++;     //        
                break;
            case 0:        //          
                Pop(opstack, ch);      // (  
                exp++;     //        
                break;
            case 1:             //      postexp 
                postexp[i++]=ch;
                Pop(opstack, ch);
                break;
            }
        }

    } //while (*exp!='\0')
    Pop(opstack, ch);
    while (ch!='=')
        //  exp    ,   '='  
    {
        postexp[i++]=ch;
        Pop(opstack, ch);
    }
    postexp[i]='\0';    // postexp         
    DestroyStack(opstack);
}

void InitStack(SqStack *&s)
{
    s=(SqStack *)malloc(sizeof(SqStack));
    s->top=-1;
}
void DestroyStack(SqStack *&s)
{
    free(s);
}
int StackLength(SqStack *s)  //        ——   
{
    return(s->top+1);
}
bool StackEmpty(SqStack *s)
{
    return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
    if (s->top==MaxSize-1)    //     ，     
        return false;
    s->top++;
    s->data[s->top]=e;
    return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
    if (s->top==-1)     //      ，     
        return false;
    e=s->data[s->top];
    s->top--;
    return true;
}
bool GetTop(SqStack *s,ElemType &e)
{
    if (s->top==-1)         //      ，     
        return false;
    e=s->data[s->top];
    return true;
}

void DispStack(SqStack *s)  //   
{
    int i;
    for (i=s->top;i>=0;i--)
        printf("%c ",s->data[i]);
    printf("
");
}
#ifndef SQSTACK_H_INCLUDED
#define SQSTACK_H_INCLUDED
#define MaxOp 7
#define MaxSize 100
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int top;                //   
} SqStack;
struct  //        
{
    char ch;   //   
    int pri;   //   
}
lpri[]= {{'=',0},{'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6}},
rpri[]= {{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};
                 //       
void trans(char *exp,char postexp[]);
int Precede(char op1,char op2);
bool InOp(char ch);
int rightpri(char op);
int leftpri(char op);
void InitStack(SqStack *&s);    //    
void DestroyStack(SqStack *&s);  //   
bool StackEmpty(SqStack *s);     //     
int StackLength(SqStack *s);  //        ——   
bool Push(SqStack *&s,ElemType e); //  
bool Pop(SqStack *&s,ElemType &e); //  
bool GetTop(SqStack *s,ElemType &e); //       
void DispStack(SqStack *s);  //   



#endif // SQSTACK_H_INCLUDED
    

<img src="http://img.blog.csdn.net/20151009081748480" alt="" />

                ，            ，    ，     ，                 ，              ，           ，    ，    ，           

                           ，                。