[栈](4.1)前、中、后缀表达式

之前接触的表达式求值的例子,是中缀转后缀运算,对应栈和队列的第21到23题,将在这儿做笔记

21题:中缀表达式转后缀表达式(由字母表示操作数)

思路:

  • 初始化两个栈,运算符栈和操作数栈,运算符栈做辅助栈
  • 从左到又扫描中缀表达式
  • 遇到操作数时,压入操作数栈
  • 遇到运算符时,判断算符栈顶的优先权

    • 若栈顶元素小于当前算符,则压入栈中
    • 若栈顶元素大于当前算符,则将栈顶元素压入操作数栈中
  • 直到达到最右边,将栈中的算符依次压入操作数栈中,输出即可

运算符优先权对照表:

此图像的alt属性为空;文件名为image.png

由于用字母代替元素,则两栈都可以用字符类型,完整测试代码如下:

#define STACKSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    char* base;
    char* top;
}SqStack;

SqStack S1, S2;

void Push(SqStack* S, char temp);
void Pop(SqStack* S, char* temp);
char Precede(char a, char b);
void InitStack(SqStack* S);
char GetTop(SqStack* S);
void visit();

int main()
{
    InitStack(&S1);
    InitStack(&S2);
    char ch, temp;
    ch = getchar();
    Push(&S2, '#');
    while (GetTop(&S2)!='#' || ch != '#')
    {
        if (ch >= 'A' && ch <= 'Z')
        {
            Push(&S1, ch);
            ch = getchar();
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
        {
            switch (Precede(GetTop(&S2), ch))
            {
            case'<':
                Push(&S2, ch);
                ch = getchar();
                break;

            case'>':
                Pop(&S2, &temp);
                Push(&S1, temp);
                break;
            case'=':
                Pop(&S2, &temp);
                ch = getchar();
                break;
            }
        }
        else
        {
            printf("表达式不合法");
        }
    }
    visit();
    system("pause");
    return 0;
}

void InitStack(SqStack *S)
{
    S->base = (char*)malloc(sizeof(char) * STACKSIZE);
    if (S->base == NULL)
    {
        exit(0);
    }
    S->top = S->base;
}
void Push(SqStack* S, char temp)
{

    *(S->top) = temp;
    S->top++;
}
void Pop(SqStack* S, char* temp)
{
    S->top--;
    *temp = *(S->top);
}
char Precede(char a, char b)//算符优先权比较
{
    char op[][7] = { { '>','>','<','<','<','>','>' },
                     { '>','>','<','<','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '>','>','>','>','<','>','>' },
                     { '<','<','<','<','<','=','0' },
                     { '>','>','>','>','0','>','>' },
                     { '<','<','<','<','<','0','=' }, };
    int i, j;
    switch (a)
    {
    case'+':
        i = 0;
        break;
    case'-':
        i = 1;
        break;
    case'*':
        i = 2;
        break;
    case'/':
        i = 3;
        break;
    case'(':
        i = 4;
        break;
    case')':
        i = 5;
        break;
    case'#':
        i = 6;
        break;
    }

    switch (b)
    {
    case'+':
        j = 0;
        break;
    case'-':
        j = 1;
        break;
    case'*':
        j = 2;
        break;
    case'/':
        j = 3;
        break;
    case'(':
        j = 4;
        break;
    case')':
        j = 5;
        break;
    case'#':
        j = 6;
        break;
    }

    if (op[i][j] == '0')
    {
        printf("表达式不合法\n");
        exit(-1);
    }
    return op[i][j];
}
char GetTop(SqStack* S)
{
    return *(S->top - 1);
}
void visit()
{
    char* p = S1.base;
    while (p < S1.top)
    {
        printf("%c", *p);
        p++;
    }
}

运算结果:

img栈顶需要压入#表示开始,输入后加#表示结束

22、对后缀表达式求值

这题跟表达式求值的思路近乎一样,具体可看表达式求值,这里主要考虑输入的是一个后缀表达式,对他进行求值。

后缀表达式没有算符优先权,就从左到右扫描,碰到操作数入操作数栈,碰到算符从操作数栈弹出两个进行运算,结果入栈,直到扫描完毕,将栈顶元素弹出,此时栈应为空,如若不为空,则是操作数过多,表达式不正确,题目给出的单个字母变量可理解为小于十的正整数,则不用链接字符串,如需链接字符串或小数点,则可以看支持浮点数运算的表达式求值,这里只记录前、中、后缀表达式之间的关系

具体测试代码如下所示:

#define STACKSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int* base;
    int* top;
}SqStack;

SqStack S1, S2;

void Push(SqStack* S, int temp);
void Pop(SqStack* S, int* temp);
void InitStack(SqStack* S);
void visit();

int main()
{
    InitStack(&S1);
    char ch;
    int a, b;
    ch = getchar();
    if (ch >= '0' && ch <= '9')
    {
        Push(&S1, ch-'0');
        ch = getchar();
        while (ch != '#')
        {
            if (ch >= '0' && ch <= '9')
            {
                Push(&S1, ch - '0');
                ch = getchar();
            }
            else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
            {
                switch (ch)
                {
                case'+':
                    Pop(&S1, &b);
                    Pop(&S1, &a);
                    Push(&S1, a + b);
                    ch = getchar();
                    break;
                case'-':
                    Pop(&S1, &b);
                    Pop(&S1, &a);
                    Push(&S1, a - b);
                    ch = getchar();
                    break;
                case'*':
                    Pop(&S1, &b);
                    Pop(&S1, &a);
                    Push(&S1, a * b);
                    ch = getchar();
                    break;
                case'/':
                    Pop(&S1, &b);
                    Pop(&S1, &a);
                    Push(&S1, a / b);
                    ch = getchar();
                    break;
                }
            }
            else
            {
                printf("表达式不正确\n");
                break;
            }
        }
    }
    else
    {
        printf("表达式不正确\n");
    }

    Pop(&S1, &a);
    if (S1.top > S1.base)
    {
        printf("表达式有误\n");
    }
    else
    {
        printf("%d", a);
    }

    system("pause");
}

void InitStack(SqStack *S)
{
    S->base = (int*)malloc(sizeof(int) * STACKSIZE);
    if (S->base == NULL)
    {
        exit(0);
    }
    S->top = S->base;
}
void Push(SqStack* S, int temp)
{

    *(S->top) = temp;
    S->top++;
}
void Pop(SqStack* S, int* temp)
{
    S->top--;
    *temp = *(S->top);
}

运行结果:

img(1+2-3+4)*2

23、判断给定的非空后缀表达式是否为正确的逆波兰式,如果是,将它转换为前缀表达式

依次扫描输入的字符串,碰到操作数则入栈,碰到运算符则取出两个操作数,联接形成子前缀 ,入栈(前后缀规则相同,一个运算符必须匹配两个操作数),则会出现两种情况:一是运算符过多,二是操作数过多。

当运算符过多的时候,没有足够的操作数来匹配,则在出栈的时候会出错。

当操作数过多的时候,没有足够的运算符来匹配,则匹配完成后栈顶元素不是最后结果。

测试代码如下所示

#define STACK_MAX 100//最大栈空间
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    char* ch;
    int length;
}String;//字符串元素

typedef struct
{
    String* base;
    String* top;
}SqStack;//栈

SqStack S;
void InitStack(SqStack *S)
{
    S->base = (String*)malloc(sizeof(String) * STACK_MAX);
    S->top = S->base;
}

void Push(SqStack* S, String T)
{
    S->top->ch = (char*)malloc(sizeof(char) * T.length + 1);
    S->top->length = T.length;
    for (int i = 1; i <= T.length; i++)
    {
        S->top->ch[i] = T.ch[i];
    }

    S->top++;
}
void Pop(SqStack* S,String *e)
{
    if (S->top < S->base)//算符过多
    {
        printf("表达式错误\n");
        system("pause");
        exit(0);
    }
    S->top--;
    e->ch = (char*)malloc(sizeof(char) * (S->top->length + 1));
    e->length = S->top->length;
    for (int i = 1; i <= S->top->length; i++)
    {
        e->ch[i] = S->top->ch[i];
    }
}

void Concat(String S, String T, String* C)
{
    if (S.length <= 0 || T.length <= 0)
    {
        printf("表达式错误\n");//算符过多
        system("pause");

        exit(0);
    }
    C->ch = (char*)malloc(sizeof(char) * (S.length + T.length + 1));
    C->length = S.length + T.length;
    int i;
    for (i = 1; i <= S.length; i++)
    {
        C->ch[i] = S.ch[i];
    }
    for (int j = 1; i <= C->length; j++, i++)
    {
        C->ch[i] = T.ch[j];
    }
}

int main()
{
    InitStack(&S);
    String s, p, a, temp, p1;
    temp.ch = (char*)malloc(sizeof(char) * 5);
    char ch;
    ch = getchar();
    while (ch != '#')
    {
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        {
            temp.length = 1;
            temp.ch[1] = ch;

            Pop(&S, &s);
            Pop(&S, &a);
            Concat(temp, a, &p);
            Concat(p, s, &p1);
            Push(&S, p1);
        }
        else
        {
            temp.length = 1;
            temp.ch[1] = ch;
            Push(&S, temp);
        }
        ch = getchar();
    }

    Pop(&S, &temp);
    if (S.top > S.base)//操作数过多
    {
        printf("表达式不正确");
    }
    else
    {
        for (int i = 1; i <= temp.length; i++)
        {
            printf("%c", temp.ch[i]);
        }
    }

    system("pause");
    return 0;
}

运行结果:

img

再次声明,后缀表达式没有优先权,别绕进去了,直接遇到算符提出来放两个操作数前面就好!!只有中缀转前缀才需要考虑优先权!!

本文链接:

https://nullcode.fun/27.html
1 + 9 =
快来做第一个评论的人吧~