数据结构实验之栈与队列二：一般算术表达式转换成后缀式

谁践踏了优雅 2024-02-18 23:03 4阅读 0赞

#### 数据结构实验之栈与队列二：一般算术表达式转换成后缀式 ####

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][] [Discuss][]

Problem Description

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

Input

输入一个算术表达式，以‘\#’字符作为结束标志。

Output

输出该表达式转换所得到的后缀式。

Sample Input

a*b+(c-d/e)*f#

Sample Output

ab*cde/-f*+

Hint

Source

思路：

由一般是求后缀式：

1.设立暂时存放运算符的栈；

2.设表达式的结束符为“\#”，设运算符的栈底为“\#”；

3.若当前字符是操作数，进栈；

4.若当前运算符的优先数高于栈顶运算符，进栈；

5.否则退出栈顶运算符发送给后缀式；

6.括号“（”对它之前之后的运算符起隔离作用，“）”可视为自相应左括号开始的表达式的结束符。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
        char a[1001];
        char b[1001];
        int len, i, top, j;
        top = 0;
        scanf("%s", a);
        len = strlen(a);
        memset(b,0,sizeof(b));
        for(i = 0; i < len - 1; i++)
        {
            if(a[i] >= 'a' && a[i] <= 'z')
            {
                printf("%c", a[i]);
            }
            else if(a[i] == '(')
            {
                top++;
                b[top] = '(';
            }
            else if(a[i] == ')')
            {
                while(b[top] != '(')
                {
                    printf("%c", b[top]);
                    top--;
                }
                top--;
    
            }
            else if(a[i] == '+' || a[i] == '-')
            {
                if(b[top] != '(' && top != 0)
                {
                    printf("%c", b[top]);
                    top--;
                }
                top++;
                b[top] = a[i];
            }
            else if(a[i] == '*' || a[i] == '/')
            {
                if(b[top] == '*' || b[top] == '/')
                {
                    printf("%c", b[top]);
                    top--;
                }
                else
                {
                    top++;
                    b[top] = a[i];
                }
            }
        }
        for(j = top; j >= 1; j--)
        {
            printf("%c", b[j]);
        }
        printf("\n");
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/2132.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/status/pid/2132.html
[Discuss]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Discuss/discusslist/pid/2132.html