用栈简单实现表达式求值

以下是使用栈简单实现表达式求值的Python代码：

def calculate(expression):
    stack = []
    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            if char == "+":
                stack.append(num1 + num2)
            elif char == "-":
                stack.append(num1 - num2)
            elif char == "*":
                stack.append(num1 * num2)
            elif char == "/":
                stack.append(num1 / num2)
    return stack.pop()

该函数接受一个字符串类型的表达式作为参数，然后遍历表达式字符，如果字符是数字，则将其转换为整数并压入栈中。如果字符是运算符，则弹出栈顶的两个数字进行相应的运算，然后将结果压入栈中。最后，栈中只剩下一个数字，即为表达式的求值结果。

相关问题

用c++语言设计算法使用栈实现简单表达式求值

在C++中，我们可以使用栈（Stack）数据结构来设计一个简单的计算器，用于计算基本的算术表达式。这种算法通常称为逆波兰表示法（Reverse Polish Notation, RPN）或后缀表达式的求值。以下是使用栈的基本步骤：

1. **输入处理**：
- 接收用户输入的表达式，通常包含加减乘除操作符和数字。

2. **预处理**：
- 将表达式转换成后缀形式，即将所有的运算符移到它们对应的操作数后面。这一步可以通过双端队列（Deque）辅助完成，从左到右扫描，遇到操作符就将它推入栈，遇到数字则直接读取。

3. **计算过程**：
- 创建一个空栈。遍历后缀表达式，对于每个元素：
- 如果是数字，压入栈；
- 否则是操作符，弹出栈顶的两个数字做相应的运算，结果再压回栈。

4. **最终结果**：
- 当处理完所有元素后，栈顶的数值即为整个表达式的计算结果。

下面是一个简单的C++函数示例：

#include <stack>
#include <string>

int evalRPN(std::string tokens) {
    std::stack<int> numbers;
    for (char token : tokens) {
        if (isdigit(token)) { // 遇到数字，直接压入栈
            numbers.push(token - '0');
        } else { // 遇到运算符
            int second = numbers.top();
            numbers.pop();
            int first = numbers.top();
            numbers.pop();
            switch (token) {
                case '+': numbers.push(first + second); break;
                case '-': numbers.push(first - second); break;
                case '*': numbers.push(first * second); break;
                case '/': {
                    double result = static_cast<double>(first) / second;
                    numbers.push(result);
                    break;
                }
                default: assert(false); // 处理未知运算符
            }
        }
    }
    return numbers.top(); // 返回栈顶结果
}

用栈实现中缀表达式求值的c++代码

在C++中，使用栈（Stack）可以实现中缀表达式的计算（逆波兰表示法，也称为后缀表达式）。这里是一个简单的例子：

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

// 定义操作数和操作的优先级
const string PRECEDENCE = "^*/+-";

int calculate(string expression) {
    stack<int> values; // 存放操作数
    stack<char> operators; // 存放运算符

    for (char c : expression) {
        if (isdigit(c)) { // 如果是数字，直接压入堆栈
            int num = 0;
            while (isdigit(c)) {
                num = num * 10 + (c - '0');
                c = getchar(); // 每次读取下一个字符
            }
            values.push(num);
        } else if (c == '(') { // 开始一个新的子表达式
            operators.push(c);
        } else if (c == ')') { // 结束子表达式并计算结果
            while (!operators.top() || PRECEDENCE[operators.top()] != '(') {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                char op = operators.top();
                values.pop();
                operators.pop();

                switch (op) {
                    case '+':
                        values.push(val1 + val2);
                        break;
                    case '-':
                        values.push(val1 - val2);
                        break;
                    case '*':
                        values.push(val1 * val2);
                        break;
                    case '/':
                        values.push(val1 / val2);
                        break;
                    default: break;
                }
            }
            operators.pop(); // 出去左括号
        } else if (prec(c, operators.top())) { // 操作符的优先级高于栈顶元素
            operators.push(c);
        } else { // 运算符优先级低于栈顶元素，出栈并计算
            while (!operators.empty() && prec(c, operators.top())) {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                char op = operators.top();
                values.pop();
                operators.pop();

                switch (op) {
                    case '+':
                        values.push(val1 + val2);
                        break;
                    case '-':
                        values.push(val1 - val2);
                        break;
                    case '*':
                        values.push(val1 * val2);
                        break;
                    case '/':
                        values.push(val1 / val2);
                        break;
                    default: break;
                }
            }
            operators.push(c);
        }
    }

    while (!operators.empty()) {
        int val2 = values.top();
        values.pop();
        int val1 = values.top();
        char op = operators.top();
        values.pop();
        operators.pop();

        switch (op) {
            case '+':
                values.push(val1 + val2);
                break;
            case '-':
                values.push(val1 - val2);
                break;
            case '*':
                values.push(val1 * val2);
                break;
            case '/':
                values.push(val1 / val2);
                break;
            default: break;
        }
    }

    return values.top(); // 返回最终结果
}

bool prec(char op1, char op2) {
    if (op2 == '(') return false;
    return PRECEDENCE.find(op1) > PRECEDENCE.find(op2);
}

int main() {
    string exp;
    cout << "请输入一个中缀表达式: ";
    getline(cin, exp);

    int result = calculate(exp);
    cout << "计算结果为: " << result << endl;

    return 0;
}

在这个示例中，我们首先读取用户输入的中缀表达式，然后通过栈结构逐步解析、计算并返回结果。