数据结构day15_C_内存溢出

C语言数据结构代码练习day15 中缀表达式转后缀表达式（带括号）

代码 *** 作
依次扫描，遇到下列情况：
1. *** 作数。

直接加入表达式中（直接输出）

2.界限符(括号)：遇到’(‘左括号直接入栈。

遇到’)‘右括号，需要d出栈中元素直到’('左括号为止。

3.运算符。

与栈顶元素进行比较。

若该字符运算优先级高，则入栈。

如果优先级低于栈顶元素，需要d出栈中优先级高于或等于当前运算符的所有字符，并直接加入表达式中（直接输出），该 *** 作当栈空或栈顶元素为‘('左括号为止，然后将当前运算符入栈。

4.扫描完全部字符并执行完以上 *** 作后，将栈中剩余元素d出并直接加入表达式中（直接输出）直至栈空。

关键点

一、将输入的运算符和运算数全视为字符，因此只能处理个位数，栈区存储char元素

二、运算符在出栈后直接加入到表达式中，可以将输出加入到出栈函数。

在后缀表达式中没有界限符（括号），因此'('出栈时不输出

三、为实现扫描到运算符时的处理中，d出运算符直至'('为止，'('的运算优先级应设为最低

四、代码 *** 3中红字 *** 作可以视为当前运算符和栈顶元素不断比较，直到遇到优先级低于当前运算符为止，因此选用栈递归调用，这也是个人认为最精髓的地方

五、扫描到‘\n’说明输入的字符串全部处理完毕，将栈中剩余元素d出

代码如下：

#include
#include

/*char顺序栈*/
typedef struct Lnode
{
    char data[20];      //存储元素
    int top;        //栈顶指针
}SqStack;

/*进栈*/
void Push(SqStack &S,char x){
    if(S.top==19)
        printf("fullerror");       //栈满
    S.top=S.top+1;      //栈顶指针移动
    S.data[S.top]=x;        //数据入栈
}

/*出栈*/
void Pop(SqStack &S,char ch){
    if(S.top==-1)
        printf("emptyerror");       //栈空
    ch=S.data[S.top];
    S.top=S.top-1;      //逻辑删除，数据仍然保留在内存中
    if(ch!='(')printf("%c",ch);
    //运算符出栈直接输出，加入到后缀表达式
}

/*运算符优先级*/
int lv(char x){
    switch (x)
    {
    case '+':
        return 1;
    case '-':
        return 1;
    case '*':
        return 2;
    case '/':
        return 2;
    case '(':
        return 0;       //优先级最低，详见关键点第三条
    }
}

/*实现运算符d出 *** 作*/
void ex(SqStack &S,char ch){
    if(lv(ch)<=lv(S.data[S.top])){      //ch运算级别小于或等于栈顶运算符
        Pop(S,S.data[S.top]);       //高于ch优先级的栈顶元素出栈
        return ex(S,ch);     //递归调用，继续比较ch和栈顶元素优先级
    }
    else        //ch运算级别大于栈顶运算符
        Push(S,ch);     //当前运算符入栈
}

int main()
{
    SqStack S;
    S.top=-1;       //初始化栈
    
    while (1)
    {
        char ch=getchar();      //依次传入字符
        if(ch=='\n'){       //扫描完毕
            while(S.top!=-1)       //d出栈中剩余元素直至栈空
                Pop(S,S.data[S.top]);
            break;
        }

        if(int(ch)>=48&&int(ch)<=57)     //ch是数字
            printf("%c",ch);
        else if(ch=='(')     //ch是'('左括号
            Push(S,ch);
        else if(ch==')')       //ch是')'右括号
        {
            while (S.data[S.top]!='(')      
                Pop(S,S.data[S.top]);       //运算符出栈直至左括号
            Pop(S,S.data[S.top]);       //左括号出栈，匹配完成
        }
        else
            ex(S,ch);       //扫描到运算符的处理，实现内容见代码 *** 作3
    }
    
    printf("\n");
    system("pause");
}

验证

输出后序遍历的表达式符合左优先原则，只会产生一种输出。

这个 *** 作与后序遍历表达式求值的代码结合，就可以实现中序遍历表达式求值，总共需要两个栈，一个存字符，一个存数值。

这里原本是想结束，但是最近确实大概弄懂getchar()这个函数了，所以还是把之前的坑给填了。

后续遍历表达式求值代码如下：

#include
#include

/*int栈*/
typedef struct Lnode
{
    int data[20];		//存储数据的栈区
    int top;		//栈顶指针
}SqStack;

/*int进栈*/
int Push(SqStack &S2,int x){
    if(S2.top==19)
        return 0;       //栈满
    S2.top=S2.top+1;      //栈顶指针移动
    S2.data[S2.top]=x;        //数据入栈
    return x;
}

/*int出栈*/
int Pop(SqStack &S2,int &x){
    if(S2.top==-1)
        return 0;       //栈空
    x=S2.data[S2.top];
    S2.top=S2.top-1;      //逻辑删除，数据仍然保留在内存中
    return x;
}

int operate(int a,char x,int b){
    switch (x)
    {
    case '+':
        return a+b;
    case '-':
        return a-b;
    case '*':
        return a*b;
    case '/':
        return a/b;
    }
}

int main()
{
    SqStack S;		//定义栈
    S.top=-1;	
    while(1)
    {
        char c=getchar();
        if(c=='\n')break;		//扫描结束		
        if(int(c)>=48&&int(c)<=57)     //c是数字
            Push(S,(int(c)-48));		//数值入栈
        else{		//c为运算符
            int a,b;
            Push(S,operate(Pop(S,a),c,Pop(S,b)));
            /*栈顶依次出栈的两个元素做c的运算，然后结果入栈*/
        }
    }
    printf("%d",S.data[S.top]);		//栈首元素即为结果
    
    printf("\n");
    system("pause");
}