// 表达式转换.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "string.h"

struct SeqStack{
    int MAXNUM;
    int t;
    char *s;};//运算符栈
typedef struct SeqStack *PSeqStack;


 


PSeqStack createEmptyStack_seq(int m)//创建空栈
{
    PSeqStack pastack=(PSeqStack)malloc(sizeof(struct SeqStack));
    if(pastack!=NULL){
        pastack->s=(char *)malloc(sizeof(char)*m);
    if(pastack->s){
        pastack->MAXNUM=m;
        pastack->t=-1;
        return(pastack);
    }
    else free(pastack);
    }
    printf("Out of Space!!\n");
    return NULL;
}
int isEmptyStack_seq(PSeqStack pastack)//判断栈是否为空
{
    return(pastack->t==-1);
}

void push_seq(PSeqStack pastack,char x)//进栈
{
    if(pastack->t>=pastack->MAXNUM-1)
        printf("Overflow!!!\n");
    else{
        pastack->t=pastack->t+1;
        pastack->s[pastack->t]=x;
    }
}

void pop_seq(PSeqStack pastack)//出栈 
{
    if(pastack->t==-1)
        printf("Underflow!!!\n");
    else
        pastack->t=pastack->t-1;
}

char top_seq(PSeqStack pastack)//取栈顶元素
{
    if(pastack->t==-1)
        printf("The Stack Is Empty!!!\n");
    else 
        return(pastack->s[pastack->t]);
}                                     //以上是栈的一系列操作
int isoperator(char op)//判断是否是操作符
{
    if(op=='*'||op=='/'||op=='+'||op=='-'||op=='(')
        return(1);
    else return(0);
}
int priority(char op)//返回操作符的优先级
{
    switch(op){
    case'*':
    case'/':  return(3);
    case'+':
    case'-':  return(2);
    case'(':  return(1);
    default:  return(0);
    }
}
int isnumber(char num)//判断是否是数字
{
    if((num>=48)&&(num<=57))
        return(1);
    else return(0);
}
char *back_expression(char *mid_expression,PSeqStack pastack)//将中缀表达式转换为后缀表达式,参数mid_expression为中缀表达式数组
{
    char back[100];                          //back为相应的后缀表达式数组
    char *Pmid=mid_expression;           //Pmid指向中缀表达式数组
    char c=*Pmid;                        //c表示中缀表达式中的一个字符
    int back_pos=0;                      //back中元素的下标
    while((c=*Pmid)!='\0')
    {
        if(c=='(') {push_seq(pastack,c);Pmid++;}//如果c是前括号,直接进入操作符栈
        else if(isnumber(c))                    //如果c是数字,直接放如back数组
        {
            back[back_pos++]=c;
            Pmid++;
        }
        else if(c==')')//如果c是后括号,则把操作符栈中前括号之前的元素全部放如back数组
        {
            while((c=top_seq(pastack))!='(')
            {
                back[back_pos++]=c;
                pop_seq(pastack);
            }
            pop_seq(pastack);//再将栈顶的前括号出栈
            Pmid++;
        }                                      
        else if(isoperator(c))          //如果c是操作符
        {
            if(isEmptyStack_seq(pastack))//操作符栈为空,则c直接入栈
            {
                push_seq(pastack,c);
                Pmid++;
            }
            else if(priority(top_seq(pastack))>=priority(c))//判断栈顶的操作符和c的优先级别
            {
                back[back_pos++]=top_seq(pastack);
                pop_seq(pastack);
                push_seq(pastack,c);
                Pmid++;
            }
            else
            {
                push_seq(pastack,c);
                Pmid++;
            }
        }
    }
    while(!isEmptyStack_seq(pastack))//将操作符栈中的剩余元素全部放入back数组
    {
        back[back_pos++]=top_seq(pastack);
        pop_seq(pastack);
    }
    back[back_pos++]='\0';
    return back;                     //返回back数组
}
int main(int argc, char* argv[])
{
    PSeqStack pastack=createEmptyStack_seq(100);
    
    char InExp[100];
    printf("请输入中缀表达式: ");
    scanf("%s",InExp);
    printf("后缀表达式为: ");
    printf("%s\n",back_expression(InExp,pastack));
    char *back1;//用一个字符串指针先存放后缀表达式
    back1=back_expression(InExp,pastack);
    

    return 0;
}