数据结构题目笔记-03-中缀表达式转为后缀表达式 C语言

后缀表达式，又称逆波兰式

指的是不包含括号，运算符放在两个运算目标的后边，所有的核算按运算符出现的次序，严格从左向右进行（不再考虑运算符的优先规矩）。

例如：后缀表达式为“2 3 + 4 x 5 -”核算过程：

1）从左向右扫描，遇到数字就压入仓库。（这儿将 2 3 压入仓库）。

2）遇到运算符号‘+’，压出栈顶开始的两个元素，核算 3 + 2 的值为5。将5再次压入仓库。

3）遇到数字4，压入仓库。

4）遇到‘x’，将栈顶开始的元素压出仓库并核算。（核算 4 x 5 = 20）。将20压入仓库。

5）遇到数字5，压入仓库。

6）最后是‘-’，压出对战中的两个元素 5 20.做核算20 – 5 得到成果为15。

中缀表达式（或中缀记法）

是一个通用的算术或逻辑公式表明办法， 操作符是以中缀方法处于操作数的中心（例：3 + 4），中缀表达式是人们常用的算术表明办法。

那么怎样将中缀表达式转化为后缀表达式呢？

1）创立一个仓库

2）从左往右次序获取中缀表达式

2.1）遇到数字，直接输出

2.2）运算符

a:遇到左括号 ‘(‘ 直接入栈

b:遇到右括号 ‘(‘，将仓库中左括号之前的元素全部压出仓库。（PS：同时左括号也压出仓库，可是我们并不打印输出）

c:遇到乘号 ‘x’ 或许除号 ‘/’ 直接入栈，直到遇到比它优先级更低的运算符，并以此压出仓库。

d:遇到加号 ‘+’ 或许减号 ‘-‘ 。假如此时是空栈，那么直接压入仓库，不然，需求将栈中优先级高的运算符号依次压出仓库（这儿需求留意的是，假如仓库中除了比它优先级高的运算符之外还有同等优先级的运算符，也要依次压出仓库）直到栈变为空或许遇到左括号停止。

e:最后，获取完毕，将剩下的运算符号依次压出仓库。

例如：将一个中缀表达式”1+((2+3)x4)-5″转化为后缀表达式的过程如下：

所以，最终的后缀表达式成果为：’1 2 3 + 4 x + 5 -‘。

代码完成：

首要，界说一个仓库。

typedef char ElementType;
typedef struct SNode *Stack;
#define INITSIZE 20
#define LEN sizeof (ElementType)
struct SNode{
    ElementType *base;指向最底
    ElementType *top;
    int StackSize;
};

创立仓库

void CreateStack(Stack S){
    S->base=(ElementType *)malloc(LEN*INITSIZE);//直接将S的base指向一个字符数组
    assert(S->base!=NULL);
    S->top=S->base;
    S->StackSize=INITSIZE;
}

压入仓库

void Push(Stack S,ElementType X){
    if(S->top - S->base>=S->StackSize){
        S->base=(ElementType*) realloc(S->base,sizeof (ElementType)*(S->StackSize+10));//空间不够就补加
        assert(S->base!=NULL);
        S->top=S->base+S->StackSize;
        S->StackSize+=10;
    }
    *S->top=X;
    S->top++;
}

回来仓库长度

int StackLength(Stack S){
    return (S->top - S->base);
}

压出仓库

int Pop(Stack S,ElementType *X){//传入的是一个地址
    if(!StackLength(S)){
        printf("栈为空\n");
        return 0;
    }
    S->top--;
    *X=*S->top;
    return 1;
}

中缀表达式转化为后缀表达式

void Change(Stack S,ElementType str[]){//核心函数
    int i=0;
    ElementType X;
    CreateStack(S);
    while (str[i]!=' '){
        while (isdigit(str[i])){
            printf("%c",str[i++]);
            if(!isdigit(str[i])){
                printf(" ");
            }
        }
        if(str[i]=='+' || str[i]=='-'){
            if(!StackLength(S)){
                Push(S,str[i]);
            } else{
                do{
                    Pop(S,&X);
                    if(X=='('){
                        Push(S,X);
                    } else{
                        printf("%c ",X);
                    }
                } while (StackLength(S) && X!='(');
                Push(S,str[i]);
            }
        } else if(str[i]==')'){
            Pop(S,&X);
            while (X!='('){
                printf("%c ",X);
                Pop(S,&X);
            }
        } else if(str[i]=='*' || str[i]=='/' || str[i]=='('){
            Push(S,str[i]);
        } else if(str[i]=='\0'){
            break;
        } else{
            printf("输入有误\n");
            return;
        }
        i++;
    }
    while (StackLength(S)){
        Pop(S,&X);
        printf("%c ",X);
    }
}

测验：

int main(void){
    ElementType str[30];
    Stack S=(Stack) malloc(sizeof (struct SNode));
    gets(str);
    Change(S,str);
    return 0;
}

留意：Stack S=(Stack) malloc(sizeof (struct SNode));这儿必须要这样写，而不是Stack S；因为我们在界说仓库的时分我们在改写别名的时分typedef struct SNode *Stack;界说的是结构体指针Stack。

关于结构体指针变量和结构体变量的不同这儿提一下。结构体变量界说的就直接是结构体，而结构体指针变量界说的是指针，必须把它和结构体联系起来才干当作结构体用，方法便是用malloc请求空间或许赋值其他目标地址，让其指向结构体。