NOJ数据结构008——逆波兰式

末蓝、 2022-11-15 14:19 158阅读 0赞

逆波兰式是数据结构中的重要内容，通过这个可以熟练栈的使用。  
本题可用单栈或双栈实现。此处笔者采用单栈的方法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
基本思路是将输入的字符串in，通过遍历筛选按顺序输入字符串out中。

遇到普通字符则直接输出到out中。

遇到操作符，则比较其与栈顶字符间的优先级（栈为空则直接入栈），优先级比栈顶高才可入栈。  
操作符优先级即 “（”、“ \* ”、“ / ” 大于“ +”、“-” 大于 ，同级之间后来输入的大于之前输入的。

则可知，遇见“（”、“ \* ”、“ / ”一定入栈，而遇见“+”、“-”则看栈顶是否为“ \* ”、“ / ”，不是则入栈。

遇到 “）”，则将栈中离其最近的一个（ 两者之间的操作符全部输出到out中。

最终遍历结束，若栈中仍有剩余字符，则按顺序输出到out中。

话不多说，上代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define Max_Stack 50
    
    typedef struct
    {
        
        char data[Max_Stack];
        int top;
    }SeqStack;
    
    void Push (char in, SeqStack *tmp)  //入栈
    {
        
        if (tmp -> top == Max_Stack) {
        
            printf("error1 ");
        }
    
        else {
        
            tmp -> top ++;
            tmp -> data[tmp -> top] = in;
        }
    }
    
    void Pop(char *out, SeqStack *tmp)  //出栈
    {
        
        if (tmp -> top > -1) {
        
            *out = tmp -> data[tmp -> top];
            tmp -> top--;
        }
        else printf("error2 ");
    }
    
    char Compare(char a, SeqStack *tmp)  //比较运算符号优先级
    {
        
        switch(a) {
        
            case '(':
            case '*':
            case '/':  {
        
                return '>';
            }
            case ')': {
        
                return '#';
            }
            case '+':
            case '-': {
        
                if (tmp -> top == -1 ||               //栈为空
                    tmp -> data[tmp -> top] == '(' ||   //栈顶优先级低
                    tmp -> data[tmp -> top] == '+' ||
                    tmp -> data[tmp -> top] == '-') {
          //或栈顶优先级低
                        return '>';
                }
                else {
                      //栈顶优先级高
                    return '<';
                }
            }
            default :{
        
                return '@';     //输入普通字符
            }
        }
    }
    
    void TransAndPrint(char in[])
    {
        
        int i, j;
        char out[100];
        SeqStack *tmp;
        tmp = (SeqStack*) malloc (sizeof(SeqStack));
        tmp -> top = -1;
        j = -1;
        for (i = 0; i < strlen(in); i++) {
        
            switch (Compare(in[i], tmp)) {
        
                case '@':{
                    //普通字符
                    j++;
                    out[j] = in[i];
                    break;
                }
                case '>':{
                    //in[i]优先级高
                    Push(in[i], tmp);
                    break;
                }
                case '<':{
                    //in[i]优先级低
                    j++;
                    Pop(&out[j], tmp);
                    i--;
                    break;
                }
                case '#': {
                  //特殊情况 遇见')'
                    while (tmp -> data[tmp -> top] != '(') {
        
                        j++;
                        Pop(&out[j], tmp);
                    }
                    tmp -> top --;
                }
            }
        }
        while (tmp -> top > -1) {
            //输出栈中剩余字符
            j++;
            Pop(&out[j], tmp);
        }
        j++;
        out[j] = '\0';      //结束字符串
        printf("%s",out);   //输出逆波兰式
    }
    
    int main()
    {
        
        char in[100];
        scanf("%s",in);
        TransAndPrint(in);
        return 0;
    }

运行截图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/6feacff1a8a541c5abe9fdf126ce4bae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/0f8f1fa6e5e1421b91fcb4bdb9b4566c.png