C++四则运算表达式求值算法

在编程领域，C++是一种广泛使用的面向对象的编程语言，其功能强大且灵活性高。四则运算表达式求值算法是计算机科学中的基础概念，它涉及到解析和计算数学中的加法、减法、乘法和除法操作。这篇文章将深入探讨如何在C++中实现一个四则运算表达式求值的算法。 我们需要理解表达式的解析过程。一个四则运算表达式可以是简单的数字之间的运算，如"2 + 3"，也可以是嵌套的复杂结构，如"(2 + 3) * 4"。解析表达式通常分为两个步骤：语法分析（词法分析）和语义分析。词法分析将输入的字符串分解为一个个有意义的单元——词法单元或记号（tokens），如数字、运算符等。语义分析则负责根据这些记号构建抽象语法树（AST），这是一种能反映表达式结构的数据结构。 C++中实现四则运算表达式求值的一个常见方法是使用栈数据结构。栈是一种后进先出（LIFO）的数据结构，非常适合处理具有优先级的运算符。我们可以遍历表达式，遇到数字时压入栈，遇到运算符时检查栈顶元素，如果当前运算符的优先级高于栈顶运算符，就将栈顶元素弹出并进行运算，结果再压入栈；如果当前运算符优先级低于栈顶运算符，则继续压入栈。遍历完成后，栈中剩下的唯一元素就是表达式的结果。 下面是一个简单的示例代码，展示了如何使用栈来实现四则运算表达式求值： ```cpp #include <stack> #include <iostream> #include <string> int precedence(char op) { // 定义运算符的优先级 if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; // 优先级为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; } } int evaluate(std::string expr) { std::stack<int> values; std::stack<char> ops; for (size_t i = 0; i < expr.size(); ++i) { if (expr[i] >= '0' && expr[i] <= '9') { int val = 0; while (i < expr.size() && expr[i] >= '0' && expr[i] <= '9') { val = val * 10 + (expr[i] - '0'); ++i; } --i; values.push(val); } else if (expr[i] == '(') { ops.push(expr[i]); } else if (expr[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)); } ops.pop(); // 弹出左括号 } else { while (!ops.empty() && precedence(ops.top()) >= precedence(expr[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.push(expr[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)); } return values.top(); } int main() { std::string expr = "3 + 5 * (2 - 1)"; std::cout << "表达式 " << expr << " 的结果是 " << evaluate(expr) << std::endl; return 0; } ``` 这段代码中，`evaluate`函数接受一个字符串形式的四则运算表达式，然后使用两个栈来处理数字和运算符。`applyOp`函数根据运算符执行相应的操作。`precedence`函数定义了运算符的优先级。 在实际应用中，为了处理更复杂的表达式，例如带有负数、浮点数、括号以及更高级的运算符，你可能需要扩展这个算法，例如通过增加对负数的支持，或者处理浮点数的运算。此外，对于更复杂的表达式，你可能还需要考虑运算符的关联性，如乘法和除法在没有括号的情况下是左结合的。 在C++编程中，理解并实现这样的四则运算表达式求值算法是基础技能之一，它可以帮助你更好地理解和处理各种计算问题。同时，这种算法也为学习编译原理和解析技术打下基础，对于编写自己的解释器或编译器是非常有用的。通过深入研究和实践，你可以掌握更多关于算法设计和数据结构的知识，进一步提升编程能力。