关于程序员:栈的应用中缀式转化为后缀式逆波兰

38次阅读

共计 1344 个字符，预计需要花费 4 分钟才能阅读完成。

1、遇到数值：间接输入

2、遇到左括号：将左括号入栈

3、遇到右括号：将栈中的运算符顺次出栈并输入，直到第一次遇到左括号（该左括号出栈但不输入）。至此打消表达式中的一对括号

4、遇到四则运算符：栈中所有优先级大于或等于该四则运算符的运算符顺次出栈并输入，而后将该运算符入栈

5、字符串遍历完结后如果栈不为空，则顺次将操作符弹出并输入

#include <iostream>
#include <stack>
#include <map>
#include <string.h>
#include <stdlib.h>
#include <cstdio>
#define is_Operand str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z'  // 判断是否为操作数
#define is_Operator str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '%' || str[i] == '@' // 判断是否为运算符
using namespace std;

string str;     // 中序输出串
char temp[100]; // 后序逆波兰式
int t = 0;      // 后序逆波兰式的无效长度

void change()
{
    stack<char> s; // 用栈来长期存储转化过程中的变量

    /// 用一个 map 来存储运算符优先级
    // 下标为字符，很有意思
    map<char, int> p;
    p['+'] = p['-'] = 1;
    p['*'] = p['/'] = p['%'] = 2;
    p['@'] = 3; // 取反操作，单目运算。优先级最高

    for (int i = 0; str[i] != '\0'; i++)
    {
        /// 首先略过空格
        if (str[i] == ' ')
            continue;

        /// 遇到左括号
        if (str[i] == '(')
            s.push(str[i]);

        /// 遇到右括号
        else if (str[i] == ')')
        {while (!s.empty() && s.top() != '(')
            {cout << s.top() << " ";
                s.pop();}
            s.pop();}

        /// 遇到操作数。反对多位整型数以及多位字符变量
        else if (is_Operand)
        {cout << str[i];
            i++;
            int res = str[i];

            // 解决多位的状况
            while (i < str.length() && is_Operand)
            {cout << str[i];
                i++;
            }
            cout << " ";
            i--;
        }

        /// 遇到运算符
        else if (is_Operator)
        {while (!s.empty() && p[s.top()] >= p[str[i]])
            {cout << s.top() << " ";
                s.pop();}
            s.push(str[i]);
        }

        /// 遇到非法符号
        else
        {
            cout << "存在非法符号";
            exit(0);
        }
    }

    /// 输入残余的操作符
    while (!s.empty())
    {cout << s.top() << " ";
        s.pop();}
}

int main()
{freopen("b.txt", "r", stdin);
    getline(cin, str);

    change(); // 将中断式转化为后缀式

    return 0;
}