C++语言中利用栈实现表达式求值 |21xrx.com

C++语言中利用栈实现表达式求值

2023-07-02 07:28:06 深夜i 14 0

C++ 栈表达式求值

在计算机科学中，表达式求值是一种非常常见的计算任务。在C++语言中，通过利用栈结构可以很方便地实现表达式求值。

首先，我们需要将中缀表达式转换成后缀表达式，也叫逆波兰表达式。一个表达式的后缀形式将操作符放在后面，这种形式便于计算机进行计算，也更容易实现代码。具体的算法可以在网上找到。简单来说，就是将中缀表达式从左到右扫描，遇到数字直接输出，而遇到操作符，就将其压入一个栈中。如果遇到左括号，则将其压入栈中。如果遇到右括号，则将栈中的操作符弹出并输出，直到遇到左括号为止。这个算法会利用到一个栈来辅助完成这个转换过程。

接下来，我们可以使用另一个栈来执行后缀表达式的计算。我们从左到右扫描后缀表达式，如果是数字，就将其压入栈中，如果是操作符，就将栈中前两个数字弹出来，进行相应的运算，并将结果压入栈中。最后，栈中剩下的数字就是最终的结果。

下面是一个C++实现的代码样例：

#include <iostream>
#include <string>
#include <stack>
#include <cmath>
using namespace std;
int eval(const string &expr) {
stack<int> numbers;
stack<char> ops;
for (int i = 0; i < expr.size(); i++) {
if (expr[i] == '(') {
ops.push(expr[i]);
} else if (isdigit(expr[i])) {
int num = 0;
while (i < expr.size() && isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
i--;
numbers.push(num);
} else if (expr[i] == ')') {
while (ops.top() != '(') {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
int result = 0;
switch (op) {
case '+': result = num1 + num2; break;
case '-': result = num1 - num2; break;
case '*': result = num1 * num2; break;
case '/': result = num1 / num2; break;
case '^': result = pow(num1, num2); break;
default: break;
}
numbers.push(result);
}
ops.pop();
} else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/' || expr[i] == '^') {
while (!ops.empty() && getPriority(ops.top()) >= getPriority(expr[i])) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
int result = 0;
switch (op) {
case '+': result = num1 + num2; break;
case '-': result = num1 - num2; break;
case '*': result = num1 * num2; break;
case '/': result = num1 / num2; break;
case '^': result = pow(num1, num2); break;
default: break;
}
numbers.push(result);
}
ops.push(expr[i]);
}
}
while (!ops.empty()) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
int result = 0;
switch (op) {
case '+': result = num1 + num2; break;
case '-': result = num1 - num2; break;
case '*': result = num1 * num2; break;
case '/': result = num1 / num2; break;
case '^': result = pow(num1, num2); break;
default: break;
}
numbers.push(result);
}
return numbers.top();
}
int getPriority(char op) {
switch (op) {
case '(': return 0;
case '+': return 1;
case '-': return 1;
case '*': return 2;
case '/': return 2;
case '^': return 3;
default: return 0;
}
}
int main() {
string expr = "1+(3-2)*2^3";
cout << eval(expr) << endl; // 输出7
return 0;
}

这份代码可以很好地处理包含四则运算和幂运算的表达式，并且还支持括号的使用。

总的来说，利用栈可以很便捷地实现表达式求值，这是计算机科学和编程中很重要的一个内容。对于C++程序员而言，这是一项必须掌握的技能。

上一篇: idea打包java可执行jar包

下一篇: C++类与对象的程序实例

评论区

相似文章