中缀表达式转后缀表达式

算法分析

运算符优先级

其中isp为栈内运算符优先级，osp为栈外运算符优先级。从表格可以看出，加减乘除运算的isp大于osp。

代码

//中缀表达式转后缀

#include<iostream>
#include<string>
#include<stack>

using namespace std;

//栈内优先级
int isp(char op) {
    int priority = 0;
    if (op == '#') {
        priority = 0;
    } else if (op == '(') {
        priority = 1;
    } else if (op == ')') {
        priority = 6;
    } else if (op == '*' || op == '/') {
        priority = 5;
    } else if (op == '+' || op == '-') {
        priority = 3;
    }
    return priority;
}

//栈外优先级
int icp(char op) {
    int priority = 0;
    if (op == '#') {
        priority = 0;
    } else if (op == '(') {
        priority = 6;
    } else if (op == ')') {
        priority = 1;
    } else if (op == '*' || op == '/') {
        priority = 4;
    } else if (op == '+' || op == '-') {
        priority = 2;
    }
    return priority;
}

bool toRPN(string &str, string &str1) {   //引用传递
    stack<char> s;                   //定义一个char类型的栈s
    s.push('#');
    int i, isPri, icPri;
    char c;
    for (i = 0; i < str.size(); i++) {
        c = str[i];
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {    //如果是数字，直接入栈
            str1 += c;
        } else {
            isPri = isp(s.top());
            icPri = icp(c);
            while (isPri > icPri) {
                str1 += s.top();
                s.pop();
                isPri = isp(s.top());
                icPri = icp(c);
            }
            if (icPri > isPri) { //入栈
                s.push(c);
            } else if (icPri == isPri) { //直接退栈
                s.pop();
            }
        }
    }
    while (!s.empty()) {      //最后，如果栈不空，则弹出所有元素并输出\
        if(s.top() != '#'){
            str1 += s.top();
        }
        s.pop();
    }
    return true;
}

int main() {                //主程序
    string from;
    string to;
    cout << "请输入中缀表达式：" << endl;
    cin >> from;
    toRPN(from, to);
    cout << "后缀表达式为：" << to << endl;
    return 1;
}

运行结果

本作品采用《CC 协议》，转载必须注明作者和本文链接