中缀表达式转换为后缀表达式·

不念不忘少年蓝@ 2022-05-18 02:07 221阅读 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*+

思路：

首先如果当前字符为数字或者是小数点就直接输出，遇到运算符并且op数组里面没有元素的时候就先把他压入到op字符串数组里面。然后继续向下走如果当前字符为运算符并且op数组里面有元素存在，则需要比较两个运算符的优先级，如果小于op练的优先级并且op里面的运算符不是（ 就输出这个运算符，如果大于就把他也压入op数组中。

最后就是当字符为 ）时，在输出在（ 之后的运算符即可。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    char op[10000];
    char s[2000];
    int judge(char c)
    {
        if(c=='+'||c=='-')return 1;
        if(c=='/'||c=='*')return 2;
        if(c=='(')return 3;
        else
            return 4;
    }
    int main()
    {
                
                scanf("%s",s);
                int top=0;
                for(int i=0; s[i]!='#';)
                {
                    if(s[i]>='a'&&s[i]<='z'||s[i]=='.')
                    {
                        while(s[i]>='a'&&s[i]<='z'||s[i]=='.')//只要当前字符为字母或小数点就直接输出；
                            printf("%c",s[i++]);
                        continue;
                    }
                    if(top==0)
                    {
                        op[++top]=s[i++];//若当前字符为运算符，就压入op中，以备后续使用。
                        continue;
                    }
                    if(judge(op[top])>=judge(s[i]))
                    {
                        while(judge(op[top])>=judge(s[i])&&top>0)
                        {
                            if(op[top]!='(')
                                printf("%c",op[top--]);
                            else
                                break;
                        }
                        op[++top]=s[i++];
                        
                    }
                    else
                    {
                        if(s[i]==')')
                        {
                            while(op[top]!='(')
                                printf("%c",op[top--]);
                            top--;
                        }
                        else
                            op[++top]=s[i];
                        i++;
                    }
                }
                while(top)
                    printf("%c",op[top--]);
    
        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