C++使用栈实现表达式求值 |21xrx.com

C++使用栈实现表达式求值

2023-06-27 18:01:39 深夜i -- --

C++ 栈表达式求值

在计算机科学中，表达式求值是一个常见的数学问题，需要计算一个由运算符和操作数组成的表达式的结果。C++是一种流行的编程语言，其提供了许多数据结构，例如栈，可用于实现表达式求值。

在C++中，我们可以使用栈来实现表达式求值。栈是一种具有后进先出（LIFO）性质的数据结构，它允许我们在栈顶执行插入和删除操作。

当我们遍历表达式时，我们可以使用一个栈来跟踪操作数和运算符。我们可以从左到右遍历操作数和运算符，并执行如下操作：

1. 如果当前元素是一个操作数，则将其推入栈中。

2. 如果当前元素是一个运算符，则将其从栈中弹出两个操作数，并使用该运算符计算结果。然后将结果推入栈中。

3. 当遍历完整个表达式后，栈顶元素将是表达式的求值结果。

这种方法的核心思想是，我们始终将操作数和运算符保存在栈中，直到我们找到另一个运算符来计算这些操作数。然后，我们将计算结果推回栈中，以便我们可以在处理下一个运算符时使用它。

下面是一个使用栈实现表达式求值的示例C++代码：


#include<stack>
#include<iostream>
using namespace std;
int evaluate(string expression) {
  stack<int> operands;
  stack<char> operators;
  for (auto c : expression) {
    if (isdigit(c)) {
      operands.push(c - '0');
    }
    else if (c == '+' || c == '-' || c == '*' || c == '/') {
      operators.push(c);
    }
    else if (c == ')') {
      int operand1 = operands.top();
      operands.pop();
      int operand2 = operands.top();
      operands.pop();
      char op = operators.top();
      operators.pop();
      if (op == '+') {
        operands.push(operand2 + operand1);
      }
      else if (op == '-') {
        operands.push(operand2 - operand1);
      }
      else if (op == '*') {
        operands.push(operand2 * operand1);
      }
      else if (op == '/') {
        operands.push(operand2 / operand1);
      }
    }
  }
  return operands.top();
}
int main() {
  string expression = "2*(3+5)-8/2";
  cout << evaluate(expression) << endl;
  return 0;
}

在上面的示例中，我们使用一个操作数栈来持有操作数，并使用一个运算符栈来持有运算符。我们从左到右遍历表达式，如果当前字符是数字，则将其推入操作数栈中，如果是一个运算符，则将其推入运算符栈中。如果当前字符是一个右括号，则我们从栈中弹出两个操作数和一个运算符来执行计算，并将结果推回操作数栈中。最终，操作数栈中的顶部元素将是表达式的求值结果。

总之，使用栈来实现表达式求值是一种常见的方法，非常适合使用C++这种编程语言。我们可以使用栈来跟踪操作数和运算符，并在找到另一个运算符时计算结果。这是一个简单且有效的方法，可以轻松地实现表达式求值。

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

下一篇: C++和C#的区别

评论区

()

相似文章