C++利用双栈实现含括号及四则运算的表达式求值算法（以#结束）

要实现一个使用栈来求解表达式的算法，我们可以采用两个栈：一个用于存储操作数（数字），另一个用于存储操作符。以下是一个C++程序的示例，实现了这个功能。 ```cpp #include <iostream> #include <stack> #include <cctype> using namespace std; // 函数原型声明 int precedence(char op); int applyOp(int a, int b, char op); int evaluateExpression(const string& expression) { stack<int> values; // 用于存储操作数 stack<char> ops; // 用于存储操作符 for (int i = 0; i < expression.length(); ++i) { if (expression[i] == ' ') continue; // 忽略空格 if (isdigit(expression[i])) { // 如果是数字，直接压入values栈 values.push(expression[i] - '0'); } else if (expression[i] == '(') { // 左括号直接压入ops栈 ops.push(expression[i]); } else if (expression[i] == ')') { // 右括号，弹出并计算直到遇到左括号 while (!ops.empty() && ops.top() != '(') { int val2 = values.top(); values.pop(); int val1 = values.top(); values.pop(); char op = ops.top(); ops.pop(); values.push(applyOp(val1, val2, op)); } // 弹出左括号 if (!ops.empty()) ops.pop(); } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') { // 处理操作符 while (!ops.empty() && precedence(ops.top()) >= precedence(expression[i])) { 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栈 ops.push(expression[i]); } else if (expression[i] == '#') { // 表达式结束，处理剩余的操作符 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)); } break; } } // 返回最终结果 return values.top(); } int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; } 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; } return 0; } int main() { string expression; getline(cin, expression); int result = evaluateExpression(expression); cout << result << endl; return 0; } ``` 代码解释 1. 函数原型声明： - `int precedence(char op);`：返回操作符的优先级。 - `int applyOp(int a, int b, char op);`：应用操作符并返回结果。 2. evaluateExpression函数： - 使用两个栈：`values`用于存储操作数，`ops`用于存储操作符。 - 遍历输入的表达式字符串，根据字符类型进行不同的处理： - 数字直接压入`values`栈。 - 左括号直接压入`ops`栈。 - 右括号弹出并计算直到遇到左括号。 - 操作符根据优先级进行处理，必要时弹出并计算。 - 表达式结束符`#`处理剩余的操作符。 3. precedence函数： - 返回操作符的优先级，加减为1，乘除为2。 4. applyOp函数： - 根据操作符执行相应的运算并返回结果。 5. main函数： - 读取输入的表达式字符串。 - 调用`evaluateExpression`函数计算结果并输出。 示例运行 输入： ``` 6-(9-3)/2-(7-1)/3# ``` 输出： ``` 1 ``` 输入： ``` 9-3*(9-7)/2-4*3# ``` 输出： ``` -6 ``` ######[AI写代码神器 | 1018点数解答 | 2024-10-19 16:12:31]