实现中缀表达式转换为后缀表达式，再求值

Mr.K

[ 本帖最后由 Mr.K 于 2014-11-9 00:04 编辑 ]\n\n#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
typedef char DataType;

//定义结构体
typedef struct snode
{
        DataType data;
        struct snode *next;
}LSNode;

//初始化
void StackInitiate(LSNode **head)
{
        *head = (LSNode *)malloc(sizeof(LSNode));
        (*head)->next = NULL;
}

//非空否
int StackNotEmpty(LSNode *head)
{
        if(head->next == NULL) return 0;
        else return 1;
}

//入栈
void StackPush(LSNode *head,DataType x)
{
        LSNode *p;
        p = (LSNode *)malloc(sizeof(LSNode));
        p->data = x;
        p->next = head->next;
        head->next = p;
}

//出栈
int StackPop(LSNode *head,DataType *d)
{
        LSNode *p = head->next;
        
        if(p == NULL)
        {
//                printf("堆栈已空出错！");
                return 0;
        }
        

        head->next = p->next;
        *d = p->data;
        free(p);
        return 1;
}

//取栈顶数据元素+修改返回栈顶元素
char StackTop(LSNode *head,DataType *d)
{
        LSNode *p = head->next;
        
        if(p == NULL)
        {
//                printf("堆栈已空出错！");
                return 0;
        }
        
        *d = p->data;
//        return 1;
        return *d;
}

//撤销动态申请空间
void Destroy(LSNode *head)
{
        LSNode *p,*p1;
        p = head;
        while(p != NULL)
        {
                p1 = p;
                p = p->next;
                free(p1);
        }


}

//后缀算术表达式的求值函数
int PostExp(char str[])
{
        DataType x,x1,x2;
        int i;
        LSNode *head;
        StackInitiate(&head);
        for(i = 0; str[i] != '#'; i++)
        {
                if(isdigit(str[i]))//???
                {
                        x = (int)(str[i]-48);//???
                        StackPush(head,x);
                }
                else
                {
                        StackPop(head,&x2);
                        StackPop(head,&x1);
                        switch(str[i])
                        {
                        case'+':{ x1 += x2; break; }
                        case'-':{ x1 -= x2; break; }
                        case'*':{ x1 *= x2; break; }
                        case'/':
                                if(x2 == 0.0)
                                {
                                        printf("除数为0错！\n");
                                        exit(0);
                                }
                                else
                                {
                                        x1 /= x2;
                                        break;
                                }
                        }
                        StackPush(head,x1);
                }
        }
        StackPop(head,&x);
        return x;
}
//////////////////////////////////////////////////////////////////////////
//验证是否为操作符
bool IsOperator(char ch)
{
        char ops[] = "+-*/";
        for(int i = 0; i < sizeof(ops); i++)
        {
                if(ch == ops[i]) return true;
        }
        return false;
}
// 比较两个操作符的优先级
int Precedence(char op1,char op2)                                        //op1代表栈顶运算符，op2代表当前扫描读到的运算符
{
        if(op1 == '#') return -1;
        if(op1 == '(') return -1;
        if(op1 == '+' || op1 == '-')
        {
                if(op2 == '*' || op2 == '/') return -1;
                else return 0;
        }
        if(op1 == '*' || op1 == '/')
        {
                if(op2 == '+' || op2 == '-') return 1;
                else return 0;
        }
        if(op1 == '+' || op1 == '-')
        {
                if(op2 == '+' || op2 == '-') return 0;
                else return -1;
        }

}

//中缀表达式转换成后缀表达式
void inFix2postFix(char *inFix,char *postFix)
{
        int len,i,j = 0;
        char c,c1;                                                               

        LSNode *head;                                                                        //定义头指针变量head
        StackInitiate(&head);                                                        //初始化链式堆栈head

        len = strlen(inFix);
        StackPush(head,'#');                                                        //将“#”压入栈顶,防止堆栈已空，报错
        for(i = 0;i < len; i++)
        {
                c = inFix[i];
        
                if(c == '(') StackPush(head,c);                                //c入栈
                else if(c == ')')                                                        //“）”任一个操作符都低级
                {
                        while(StackTop(head,&c1) != '(')                //取栈顶元素
                        {
                                postFix[j++] = StackTop(head,&c1);  //将在“（”之后的操作符放到后缀表达式
                                StackPop(head,&c1);                                    //并把它出栈
                        }
                        StackPop(head,&c1);                                            //把“（”出栈
                }
                else
                {
                        if(!IsOperator(c))postFix[j++] = c;     //条件：不是操作符（即操作数），执行第一条语句
                        else
                        {        
                                
                                if(StackTop(head,&c1) == '#')
                                {
                                        StackPush(head,c);                                //将操作符压入栈顶                                       
                                }
                                else
                                {
                                        while(StackNotEmpty(head) == 1               
                                                && Precedence(StackTop(head,&c1),c) >= 0)
                                        {
                                                postFix[j++] = StackTop(head,&c1);
                                                StackPop(head,&c1);
                                        }
                                        StackPush(head,c);                                  //将操作符压入栈顶
                                }
                                
                        }

                }
        }
        while(StackNotEmpty(head) == 1)                                 //弹出所有操作符
        {
                postFix[j++] = StackTop(head,&c);
                StackPop(head,&c1);
        }

        postFix[j] = '\0';                                                        //字符数组添加结束符
}
//////////////////////////////////////////////////////////////////////////


void main(void)
{
        char str[] = "3642/-5*+#",str1[] = "3+(6-4/2)*5",str2[20];        
        inFix2postFix(str1,str2);                                                //对中缀表达式进行转换，再计算
        int result,result2;
        printf("%s\n",str2);

        result = PostExp(str);
        result2 = PostExp(str2);
        printf("\n\n\n\n（直接对后缀表达式的运算）后缀算术表达式计算结果：%d\n",result);
        printf("\n\n\n\n（间接对中缀表达式的运算）后缀算术表达式计算结果：%d\n",result2);
}