用cpp写波兰式和逆波兰式的代码

波兰式和逆波兰式是数学表达式的两种常见写法，其中波兰式又叫前缀表达式，逆波兰式又叫后缀表达式。下面是用C++实现波兰式和逆波兰式的代码示例。

1.波兰式转换：

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

using namespace std;

int priority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infix2prefix(string infix) {
    string prefix;
    stack<char> opStack;

    for (int i = infix.length() - 1; i >= 0; i--) {
        char c = infix[i];

        if (isalnum(c)) {
            prefix = c + prefix;
        }
        else if (c == ')') {
            opStack.push(c);
        }
        else if (c == '(') {
            while (opStack.top() != ')') {
                prefix = opStack.top() + prefix;
                opStack.pop();
            }
            opStack.pop();
        }
        else {
            while (!opStack.empty() && priority(opStack.top()) > priority(c)) {
                prefix = opStack.top() + prefix;
                opStack.pop();
            }
            opStack.push(c);
        }
    }

    while (!opStack.empty()) {
        prefix = opStack.top() + prefix;
        opStack.pop();
    }

    return prefix;
}

int main() {
    string infix = "(1+2)*3-4/5";
    string prefix = infix2prefix(infix);
    cout << prefix << endl;
    return 0;
}

2.逆波兰式转换：

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

using namespace std;

int calculate(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

int evalRPN(string tokens) {
    stack<int> numStack;

    for (int i = 0; i < tokens.length(); i++) {
        char c = tokens[i];

        if (isdigit(c)) {
            int num = c - '0';
            while (isdigit(tokens[i+1])) {
                num = num * 10 + (tokens[i+1] - '0');
                i++;
            }
            numStack.push(num);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            int b = numStack.top();
            numStack.pop();
            int a = numStack.top();
            numStack.pop();
            numStack.push(calculate(a, b, c));
        }
    }

    return numStack.top();
}

string infix2postfix(string infix) {
    string postfix;
    stack<char> opStack;

    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];

        if (isdigit(c)) {
            postfix += c;
        }
        else if (c == '(') {
            opStack.push(c);
        }
        else if (c == ')') {
            while (opStack.top() != '(') {
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.pop();
        }
        else {
            while (!opStack.empty() && opStack.top() != '(' && priority(opStack.top()) >= priority(c)) {
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.push(c);
        }
    }

    while (!opStack.empty()) {
        postfix += opStack.top();
        opStack.pop();
    }

    return postfix;
}

string infix2RPN(string infix) {
    string postfix = infix2postfix(infix);
    return postfix;
}

int main() {
    string infix = "(1+2)*3-4/5";
    string postfix = infix2RPN(infix);
    int res = evalRPN(postfix);
    cout << res << endl;
    return 0;
}