写一下逆波兰式的伪代码

当我问你我在前面对你说了什么时，为了娱乐效果，我将讲一个笑话：

有一只鳄鱼在河里游泳，突然发现河里的水变得很浅，于是它很不满地说：“这边的水太浅了，我要去找深一点的地方。”于是它游到河的另一侧，发现那里的水更浅，于是它又说：“这边的水也太浅了，我得再游远点。”然后它游到了整个河流的另一端，才发现原来它一直在沙滩上爬行。

关于你的问题，这是逆波兰式的伪代码：

1. 设置空栈stack
2. 读入中缀表达式
3. 依次扫描中缀表达式的每个元素：
4. 如果是数字，将数字压入stack
5. 如果是运算符，弹出栈顶的两个元素temp1和temp2，执行运算，并将结果压回stack
6. 最后，栈顶的元素即为逆波兰式表达式的值

相关问题

用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;
}

逆波兰式动画演示代码

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

bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

int performOperation(char operation, int operand1, int operand2) {
    if (operation == '+') {
        return operand1 + operand2;
    } else if (operation == '-') {
        return operand1 - operand2;
    } else if (operation == '*') {
        return operand1 * operand2;
    } else if (operation == '/') {
        return operand1 / operand2;
    }
    return -1;
}

int evaluatePostfix(string exp) {
    stack<int> s;
    for (char& c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else if (isOperator(c)) {
            int operand2 = s.top();
            s.pop();
            int operand1 = s.top();
            s.pop();
            int result = performOperation(c, operand1, operand2);
            s.push(result);
        }
    }
    return s.top();
}

int main() {
    string exp = "231*+9-";
    cout << "The result of evaluation is: " << evaluatePostfix(exp);
    return 0;
}