中缀表达式转后缀表达式的方法

痛定思痛。 2023-03-04 14:25 133阅读 0赞

### 表达式求值： ###

**1.从左到右进行遍历**  
**2.运算数**,直接输出.  
**3.左括号**,直接压入堆栈,(括号是最高优先级,无需比较)(**入栈后优先级降到最低**,确保其他符号正常入栈)  
**4.右括号**,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)  
**5.运算符**,将该运算符与栈顶运算符**进行比较**,  
如果**优先级高于栈顶运算符**则压入堆栈(该部分运算还不能进行),  
如果**优先级低于等于栈顶运算符**则将栈顶运算符弹出并输出,然后比较新的栈顶运算符.  
(低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)  
直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.  
**6.如果对象处理完毕**,则按顺序弹出并输出栈中所有运算符.

如何将中缀转后缀思路： 假如表达式是一个字符串

创建一个符号栈和一个字符串队列

遍历各个字符信息

判断该字符是 运算符、括号、数值

*  运算符
    
    判断当前字符优先级是否小于等于栈顶字符优先级，此时栈顶元素中的左括号(，优先级最小
    
     *  小于等于 将符号栈栈顶内容弹出且存入到字符串队列中,将当前字符存入到符号栈中
     *  大于将当前字符存入到符号栈中
 *  括号
    
     *  左括号存入到符号栈中
     *  右括号 依次将符号栈中的运算符弹出进入到字符串队列中直到在符号栈中弹出出现左括号停止弹栈 数值 直接进入到字符串队列中
 *  数值
    
    直接输出

遍历结束后 判断符号栈中是否有元素

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    #define MAX 1000
    char *change(char data[]);
    bool compare(char a, char b);
    int priority(char a);
    // (40  括号在算术上优先级最高，但是在 栈的优先级是最低的，为了其他符号正常入栈 优先级最低
    //  /* 优先级最高 , +- 优先级最低
    
    // true 的情况 只有a 是*/ b是+-的情况
    int priority(char a)
    {
        if (a == '(')
        {
            return 0;
        }
        else if (a == '+' || a == '-')
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }
    // 比较优先级 ,a 的优先级比b 高，就返回true
    bool compare(char a, char b)
    {
        return priority(a) > priority(b);
    }
    // 中缀表达式--> 后缀表达式(逆波兰表达式)
    // 返回字符串数组
    char *change(char data[])
    {
    
        char *hou = (char *)malloc(MAX * sizeof(char));
        stack<char> s;
        int index = 0; // 后缀表达式的长度
        int length = strlen(data);
        // 1. 判断类型
        for (int i = 0; i < length; i++)
        {
            // 如果是运算数，直接输出，
            if (data[i] >= '0' && data[i] <= '9')
            {
                hou[index] = data[i];
                index++;
            }
            else if (data[i] == ')')
            {
                // 不断的弹出栈元素并输出直到遇到左括号结束
                while (!s.empty() && s.top() != '(')
                {
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.pop(); //退出左括号
            }else if(data[i]=='('){
                 s.push(data[i]);
            }
            else
            {
                // 表示 运算符优先级小于等于 栈顶元素,就退出栈顶元素，并输出
                // 包含情况data[i]='(',compare 返回false
                
                while (!s.empty() && !compare(data[i], s.top()))
                {
                    printf("%c %c %d\n",data[i],s.top(),compare(data[i], s.top()));
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.push(data[i]);
            }
            printf("此时输出内容 %-20s \t参加运算的符号 %c  \t\t栈的元素个数%d \n", hou, data[i], s.size());
        }
    
        // 输出栈内所有元素
        while (!s.empty())
        {
            hou[index] = s.top();
            index++;
            s.pop();
        }
        return hou;
    }
    
    // 后缀表达式的计算
    int main(int argc, char const *argv[])
    {
        // 样例 2*(9+6/3-5)+4
        // 结果 2963/+5-*4+
        char s[MAX] = "2*2*2*2+2";
        char *result;
        result = change(s);
        printf("%s\n", result);
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1amluZzFfMQ_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1amluZzFfMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/12746c96a90c4e5f973dc14c48bfc209.png