用栈实现算数表达式的求值

好的，这是一个计算机科学问题，非常适合我作为AI进行回答。使用栈可以方便地实现算术表达式的求值。具体实现方式为：将中缀表达式转换成后缀表达式，在栈中使用一个运算符栈和一个操作数栈，扫描后缀表达式，遇到操作数则入栈，遇到运算符则弹出操作数，进行运算后将结果入栈，最后操作数栈中的唯一元素即为表达式的结果。

相关问题

利用顺序栈完成算数表达式求解的C语言代码

在C语言中，利用顺序栈（数组实现）计算简单的算术表达式通常涉及前缀（prefix）表示法或者逆波兰表示法（RPN，也称后缀表示法）。这里是一个基于逆波兰表示法的简单示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STACK_SIZE 100

int is_digit(char c) {
    return ('0' <= c && c <= '9');
}

int pop(stack_t *s) {
    if (s->top == -1) {
        return INT_MIN;
    }
    int top_val = s->data[s->top];
    s->top--;
    return top_val;
}

void push(stack_t *s, int val) {
    if (s->top >= MAX_STACK_SIZE - 1) {
        printf("Stack overflow.\n");
        return;
    }
    s->data[++s->top] = val;
}

int eval_rpn(const char *tokens) {
    stack_t s = { -1 };
    const char *token = tokens;
    while (*token != '\0') {
        if (is_digit(*token)) {
            int num = 0;
            while (is_digit(*++token)) {
                num = num * 10 + *token - '0';
            }
            push(&s, num);
        } else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch (*token++) {
                case '+':
                    push(&s, op1 + op2);
                    break;
                case '-':
                    push(&s, op1 - op2);
                    break;
                case '*':
                    push(&s, op1 * op2);
                    break;
                case '/':
                    if (op2 != 0)
                        push(&s, op1 / op2);
                    else
                        printf("Division by zero error.\n");
                    break;
                default:
                    printf("Invalid operator.\n");
                    return INT_MIN;
            }
        }
    }
    return pop(&s);
}

int main() {
    char expression[] = "2 3 + 4 *";
    int result = eval_rpn(expression);
    printf("Result of the expression: %d\n", result);

    return 0;
}

在这个代码中，我们首先检查字符是否为数字，如果是则读取直到遇到非数字字符，然后将整数值推入栈。遇到操作符时，从栈顶弹出两个操作数进行相应的运算，并把结果压回栈。最后栈顶剩余的就是表达式的计算结果。

利用栈实现简单算数表达式求值c++

利用栈（Stack）实现简单算术表达式求值通常涉及到逆波兰表示法（Reverse Polish Notation, RPN），也被称为后缀表达式。C++中通过迭代器遍历输入字符串，并使用两个栈分别处理操作符和操作数：

1. **解析输入表达式**：将中缀表达式转换成后缀表达式，遇到数字直接压入操作数栈，遇到运算符则将其推到运算符栈。

2. **计算求值**：从后往前遍历后缀表达式的每个元素，当遇到一个数字时，弹出最近的运算符并进行相应的运算（如加减乘除），然后将结果压回操作数栈。这个过程一直持续到只剩下一个元素。

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

std::string precedence(char op) {
    if (op == '+' || op == '-') return "left";
    if (op == '*' || op == '/') return "right";
}

int applyOp(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 注意这里需要判断除数是否为零
    }
}

int evaluate(std::string tokens) {
    std::stack<int> values;
    std::stack<char> ops;

    for (char token : tokens) {
        if (isdigit(token)) {
            values.push(stoi(token));
        } else {
            while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
                int val2 = values.top(); values.pop();
                int val1 = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            ops.push(token);
        }
    }

    while (!ops.empty()) {
        int val2 = values.top(); values.pop();
        int val1 = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        values.push(applyOp(val1, val2, op));
    }

    return values.top();
}

int main() {
    std::string expression = "4 + 5 * 6"; // 示例表达式
    std::cout << "Result of expression: " << evaluate(expression) << std::endl;
    return 0;
}