上篇博客逆波兰表达式介绍了逆波兰表达式和如何计算逆波兰表达式，我们知道，用代码实现计算逆波兰表达式是相对于直接计算中缀表达式是比较简单的。但如何每次计算都需要手动转换为逆波兰表达式就比较麻烦，因此这篇博客就是介绍如何将中缀表达式转换为逆波兰表达式。
 

中缀表达式

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

与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。

与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
 

中缀转逆波兰

 

  1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
  2. 从左至右扫描中缀表达式；
  3. 遇到操作数时，将其压s2；

  4. 遇到运算符时，比较其与s1栈顶运算符的优先级：

    • 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
    • 否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
    • 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
  5. 遇到括号时：
    • 如果是左括号“(”，则直接压入s1；
    • 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
  6. 重复步骤2至5，直到表达式的最右边；
  7. 将s1中剩余的运算符依次弹出并压入s2；
  8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）
     

c语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
while( c != '#')
 {
     while(c>='0'&&c<='9')
    {
        printf("%c",c);
        scanf("%c",&c);
        if(c<'0'||c>'9')
        printf(" ");

    }
    if(')'==c)
    {
        pop(&s,&e);
        while('(' != e)
        {
            printf("%c ",e);
            pop(&s,&e);
        }
    }
    else if('+'==c||'-'==c)
    {
        if( !StackLen(s))
        {
            push(&s,c);
        }
        else
        {
            do
            {
                pop(&s,&e);
                if('('==e)
                {
                    push(&s,e);
                }
                else
                {
                    printf("%c ",e);
                }
            }while(StackLen(s)&&'('!=e);
            push(&s,c);
        }
    }
    else if('*'==c||'/'==c||'('==c)
    {
        push(&s,c);
    }
    else if(c=='#')
    {
        break;
    }
    else
    {
        printf("\n出错：输入格式错误！\n");
        return -1;
    }

    scanf ("%c ",&c);
}
while(StackLen(s))
{
    pop(&s,&e);
    printf("%c ",e);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

InitStack(sqStack *s)		//初始化栈
{
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof (ElemType));
    if (!s->base)
        exit (0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

push(sqStack *s,ElemType e)		//入栈
{
    //如果栈空，追加空间
    if (s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if( !s->base )
            exit(0);
        s->top = s->base + s->stackSize;
        s->stackSize = s->stackSize + STACKINCREMENT;
    }
    *(s->top) = e;
    s->top++;
}

ClearStack(sqStack *s)		//清空栈
{
    s->top = s->base;
}

DestroyStack(sqStack *s)		//销毁栈
{
    int i,len;
    len = s->stackSize;
    for(i = 0;i<=len;i++)
    {
        free(s->base);
        s->base++;
    }
    s->base = s->top =NULL;
    s->stackSize = 0;
}

int StackLen(sqStack s)		//返回栈长度
{
    return(s.top - s.base );
}

pop(sqStack *s,ElemType *e)		//出栈
{
    if(s->top == s->base )
        return ;
    *e = *--(s->top);
}

int main()
{
    sqStack s;
    char c,e;
    InitStack(&s);

    printf("请输入中缀表达式，以#作为结束标志：");
    scanf ("%c",&c);
    while( c != '#')
    {
        while(c>='0'&&c<='9')
        {
            printf("%c",c);
            scanf("%c",&c);
            if(c<'0'||c>'9')
            printf(" ");

        }
        if(')'==c)
        {
            pop(&s,&e);
            while('(' != e)
            {
                printf("%c ",e);
                pop(&s,&e);
            }
        }
        else if('+'==c||'-'==c)
        {
            if( !StackLen(s))
            {
                push(&s,c);
            }
            else
            {
                do
                {
                    pop(&s,&e);
                    if('('==e)
                    {
                        push(&s,e);
                    }
                    else
                    {
                        printf("%c ",e);
                    }
                }while(StackLen(s)&&'('!=e);
                push(&s,c);
            }
        }
        else if('*'==c||'/'==c||'('==c)
        {
            push(&s,c);
        }
        else if(c=='#')
        {
            break;

        }
        else
        {
            printf("\n出错：输入格式错误！\n");
            return -1;
        }

        scanf ("%c ",&c);
    }
    while(StackLen(s))
    {
        pop(&s,&e);
        printf("%c ",e);
    }
    return 0;
}

下篇计算中缀表达式

 

– ©博主原创，转载请注明出处 –

最后更新： 2019年08月21日 14:38

原始链接： https://yuanspace.top/2019/08/20/RNM/

赏
× 请我吃糖~
打赏二维码