逆波兰表达式

逆波兰表达式又称作后缀表达式，是一种便于计算机运算的数学表达式，我们日常使用的中缀表达式需要用括号确定优先级，而后缀表达式是不需要括号的

中缀表达式转后缀表达式

手写实现转换

比如想把(3+5)*4+6/(8-5)转为后缀表达式

1. 为所有运算符加括号

   (3+5)*4+6/(8-5)—–>(((3+5)*4)+(6/(8-5)))

2. 将运算符移至")"之后

   (((3+5)*4)+(6/(8-5)))—–>(((35)+4)*(6(85)-)/)+

3. 去除所有括号

   (((35)+4)*(6(85)-)/)+—–>35+4*685-/+

即最终结果为35+4*685-/+

C++实现转换

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

using namespace std;

// 判断是否为括号
bool isBracket(char c) {
    return (c == '(' || c == ')') ? true : false;
}

// 获得符号的优先性
int getPri(char c)
{
    switch (c) {
    case '+':
    case '-':
        return 0;   // 如果是加减，返回0
        break;
    case '*':
    case '/':
        return 1;   // 如果是乘除，返回1
        break;
    case '(':
    case ')':
        return -1;  // 这里将括号设为最低优先级，因此括号不会被弹出，除非遇到右括号
        break;
    default:
        cout << "输入其他运算符\n" << endl;
    }
}

//判断符号的优先性
void check(char c, stack<char>& operator_s, string& suffix) {
    if (operator_s.empty()) {
        operator_s.push(c);
        return;
    }
    
    if (isBracket(c)) {
        if (c == '(') {
            operator_s.push(c);
        }
        else {
            // 弹出所有元素直到遇到左括号
            while (operator_s.top() != '(') {
                suffix += operator_s.top();
                operator_s.pop();
            }

            // 遇到左括号，弹出且不加入后缀表达式
            operator_s.pop();
        }
    }
    else {
        // 如果不是括号，比较当前元素，与栈顶元素的优先级
        if (getPri(c) > getPri(operator_s.top())) {
            operator_s.push(c);
        }
        else {
            // 弹栈直到优先级大于栈顶元素优先级
            while (!operator_s.empty() && getPri(operator_s.top()) >= getPri(c)) {
                suffix += operator_s.top();
                operator_s.pop();
            }
            operator_s.push(c);
        }
    }
}

// 中缀表达式转后缀表达式
string infixToSuffix(string& infix) {
    stack<char> operator_s; // 运算符栈
    string suffix;          // 后缀表达式

    //int num = 0;
    for (int i = 0; i < infix.size(); ++i) {
        if (infix[i] >= '0' && infix[i] <= '9') {
            suffix += infix[i];
        }
        else {
            check(infix[i], operator_s, suffix);
        }
    }

    // 对中缀表达式的遍历结束，将栈中元素加入后缀表达式
    while (!operator_s.empty()) {
        suffix += operator_s.top();
        operator_s.pop();
    }

    return suffix;
}

int main()
{
    string s = "2*5+6*(7-8)+6";
    cout << s << endl;

    string suffix = infixToSuffix(s);
    cout << suffix << endl;
}

后缀表达式求值

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    string s = "35+4*685-/+";
    stack<char> st;
    int value = 0;
    cout << s << endl;

    for (int i = 0; i < s.size(); i++)
    {
        if('0'<=s[i]&&'9'>=s[i])
        {
            st.push(s[i]);
        }
        else
        {
            if('+'==s[i])
            {
                int b = st.top() - '0';
                st.pop();
                int a = st.top() - '0';
                st.pop();
                char t = a + b + '0';
                st.push(t);
            }
            else if('-'==s[i])
            {
                int b = st.top() - '0';
                st.pop();
                int a = st.top() - '0';
                st.pop();
                char t = a - b + '0';
                st.push(t);
            }
            else if('*'==s[i])
            {
                int b = st.top() - '0';
                st.pop();
                int a = st.top() - '0';
                st.pop();
                char t = a * b + '0';
                st.push(t);
            }
            else if('/'==s[i])
            {
                int b = st.top() - '0';
                st.pop();
                int a = st.top() - '0';
                st.pop();
                char t = a / b + '0';
                st.push(t);
            }
        }
    }

    value = st.top() - '0';
    st.pop();

    cout << "value = " << value << endl;
}