c++栈做表达式求值

C语言中的栈可以用来实现表达式的求值。在表达式求值时，我们使用两个栈，一个用来存放操作数，另一个用来存放操作符。我们从左至右遍历表达式，遇到操作数就直接入操作数栈，遇到操作符就与操作符栈顶比较优先级，如果当前操作符的优先级高于操作符栈顶元素的优先级，就直接入操作符栈，如果当前操作符的优先级低于或等于操作符栈顶元素的优先级，就取出操作数栈中的两个操作数和操作符栈中的操作符进行计算，并将结果入操作数栈，直到当前操作符的优先级高于操作符栈顶元素的优先级，再将当前操作符入操作符栈。

当表达式遍历完后，如果操作符栈中还有操作符，则取出操作数栈中的两个操作数和操作符栈中的操作符进行计算，直到操作符栈为空，此时操作数栈中只剩下一个元素，即为表达式的值。

通过使用栈来实现表达式求值，可以很好地处理操作符的优先级和括号的嵌套，保证了表达式求值的正确性。同时，栈的先入后出的特性也符合表达式中操作符的计算顺序，使得代码实现简洁高效。

总之，使用C语言中的栈来做表达式求值是一种简单而有效的方法，能够解决各种表达式的求值问题。

相关问题

c++用栈实现表达式求值

栈可以用来实现表达式求值算法。算法的主要思路是遍历表达式，当遇到数字时将其入栈，当遇到操作符时，从栈中取出相应的操作数进行计算，将计算结果再次入栈，直到遍历结束。

具体步骤如下：
1. 初始化一个空栈，用来存放数字和中间计算结果。
2. 遍历表达式的每一个字符：
a. 如果字符是数字，将其转换为数字并入栈。
b. 如果字符是操作符，取出栈顶的两个数字进行计算，并将计算结果入栈。
3. 最后栈中剩下的就是表达式的最终结果。

例如，对于表达式"5+(3-1)*2"：
1. 遍历字符"5"，将其入栈。
2. 遍历字符"+"，取出栈顶的数字5和操作符"+"，无需计算。
3. 遍历字符"("，将其入栈。
4. 遍历字符"3"，将其入栈。
5. 遍历字符"-"，取出栈顶的数字3和操作符"-"，无需计算。
6. 遍历字符"1"，将其入栈。
7. 遍历字符")"，取出栈顶的数字1和操作符"-"，计算结果为2，并将结果入栈。
8. 遍历字符"*"，取出栈顶的数字5和操作符"*"，计算结果为10，并将结果入栈。
9. 遍历结束，栈中剩下的数字10就是表达式的最终结果。

通过使用栈来实现表达式求值，可以保持操作符的优先级和括号的顺序，确保表达式求值的正确性。同时，栈的特性能够很好地支持表达式的计算过程。

C++利用栈进行表达式求值

使用栈计算表达式的一般方法是将中缀表达式转换为后缀表达式，然后再用后缀表达式计算结果。下面是一个简单的 C++ 代码实现：

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

using namespace std;

// 判断是否为数字
bool isDigit(char c) {
    return c >= '0' && c <= '9';
}

// 判断是否为运算符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取运算符优先级
int getPriority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

// 计算两个数的结果
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;
    }
}

// 将中缀表达式转换为后缀表达式
string toPostfix(string infix) {
    stack<char> s;
    string postfix;
    for (int i = 0; i < infix.size(); i++) {
        char c = infix[i];
        if (isDigit(c)) { // 数字直接输出
            postfix += c;
        } else if (isOperator(c)) { // 运算符入栈，遇到优先级更低的运算符就弹出
            while (!s.empty() && isOperator(s.top()) && getPriority(s.top()) >= getPriority(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        } else if (c == '(') { // 左括号直接入栈
            s.push(c);
        } else if (c == ')') { // 右括号弹出栈顶元素直到遇到左括号
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if (!s.empty()) {
                s.pop();
            }
        }
    }
    while (!s.empty()) { // 将剩余的运算符弹出
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

// 计算后缀表达式的结果
int evaluatePostfix(string postfix) {
    stack<int> s;
    for (int i = 0; i < postfix.size(); i++) {
        char c = postfix[i];
        if (isDigit(c)) { // 数字入栈
            s.push(c - '0');
        } else if (isOperator(c)) { // 弹出栈顶的两个数进行计算，并将结果入栈
            int b = s.top();
            s.pop();
            int a = s.top();
            s.pop();
            s.push(calculate(a, b, c));
        }
    }
    return s.top();
}

// 计算中缀表达式的结果
int evaluateInfix(string infix) {
    string postfix = toPostfix(infix);
    return evaluatePostfix(postfix);
}

int main() {
    string infix = "3+4*5/(2-1)";
    cout << infix << " = " << evaluateInfix(infix) << endl; // 输出结果为 23
    return 0;
}

上述代码中，`toPostfix` 函数将中缀表达式转换为后缀表达式，`evaluatePostfix` 函数计算后缀表达式的值，`evaluateInfix` 函数计算中缀表达式的值。这里使用了两个栈，一个栈用于将运算符转换为后缀表达式，另一个栈用于计算后缀表达式的值。