中缀表达式转化为后缀表达式(栈思想)

ゞ浴缸里的玫瑰 2021-11-17 11:40 393阅读 0赞

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

Problem Description

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

Input

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

Output

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

Sample Input

***ab+(c-d/e)f\#***

Sample Output

**ab*cde/-f*\+**

**代码展示：**

#include<bits/stdc++.h>
    using namespace std;
    
    int judge(char a,char b)
    { 
        if(b=='(')
        { 
            return 1;
        }
        else if((a=='%'||a=='*'||a=='/')&&(b=='+'||b=='-'))
        { 
            return 1;
        }
        else
            return 0;
    }
    
    int main()
    { 
        char a[10000];
        scanf("%s",a);
        int n=strlen(a);
        stack <char> q;
        int i;
        for(i=0;i<n;i++)
        { 
            if(a[i]>='a'&&a[i]<='z')
            { 
                printf("%c",a[i]);
            }
            else if(a[i]=='#')
            { 
                while(!q.empty())
                { 
                    printf("%c",q.top());
                    q.pop();
                }
            }
            else
            { 
                if(q.empty())
                { 
                    q.push(a[i]);
                }
                else
                { 
                    if(a[i]=='(')
                        q.push(a[i]);
                    else if(a[i]==')')
                    { 
                        while(q.top()!='(')
                        { 
                            printf("%c",q.top());
                            q.pop();
                        }
                        q.pop();
                    }
                    else if(judge(a[i],q.top())>0)
                    { 
                        q.push(a[i]);
                    }
                    else
                    { 
                        printf("%c",q.top());
                        q.pop();
                        q.push(a[i]);
                    }
                }
            }
        }
        return 0;
    }

**步骤说明：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]  
***举例说明***

a\*(b+c)/d 转化为后缀表达式为：abc+\*d/

变化过程为：

1、碰到运算数a就输出；![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 1]  
2、碰到 \* 号放入栈![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 2]  
3、碰到左括号，左括号的优先级比\*号的优先级高，so把左括号放进栈中；![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 3]  
4、碰到运算数b，直接输出；![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 4]  
5、当左括号放进栈中的时候，优先级降到最低，so+号的优先级比左括号高，放进栈中，并把c输出；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 5]  
6、当碰到右括号的时候，把栈顶的元素以此依次输出知直到碰到左括号结束，把左括号从栈中删除；![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 6]  
7、碰到 / 号,除法的优先级和乘法相同，但是要按照从左到右的原则，so输出 \* ，把 / 号放进栈中；然后输出运算数d；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 7]  
8、运算截止，把栈中的所有元素全部输出；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 8]  
**时间复杂度：** **O（n）**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]: /images/20211116/c4e0c57badb94d369a577ff4d89d8d4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 1]: /images/20211116/18fcb956cbdd40ecbadeeafcc798f50d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 2]: /images/20211116/e06db22d7c164e1d8ffbe428f578101a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 3]: /images/20211116/eb441a3eb4664c5e84e1ba82bad432bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 4]: /images/20211116/3a3aac38c6f142f19633c99212ac9e24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 5]: /images/20211116/6cc788dd893340a0a7784d165dcae84d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 6]: /images/20211116/eef2392a097c4a428f17fb52dcdccebf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 7]: /images/20211116/f132eecd50dd41dda13e9d1dc38868d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 8]: /images/20211116/a427021daa16497ab5c03e9acc2dfba3.png