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

C++栈实现表达式求值

2023-07-13 17:58:02 深夜i -- --

C++ 栈表达式求值

在计算机科学中，栈是一种常用的数据结构，被广泛应用于表达式求值、括号匹配等问题中。使用C++语言可以轻松实现栈数据结构，并使用它来解决表达式求值问题。

在表达式求值中，我们需要构建一个表达式树，然后遍历这棵树来计算表达式的结果。表达式树是由操作符和操作数构成的二叉树，其中每个叶节点都是一个操作数，每个非叶节点都是一个操作符。例如，在一个简单的表达式“2 + 3 * 4”中，操作数是2、3和4，操作符是“+”和“*”。

有了表达式树之后，我们需要实现求值算法。基本思想是从根节点开始遍历树，在遇到一个操作符节点时，将其左右子树中的值通过该操作符计算得到一个中间结果，然后再用该中间结果代替原来的子树。最终，遍历结束后树的根节点存储的就是表达式的计算结果。

现在，我们来实现栈来帮助我们构建表达式树和计算表达式的结果。栈可以用C++ STL库中的stack实现，也可以自定义一个栈类。这里我们采用自定义栈类的方式。

首先，我们定义一个节点类，表示栈中的一个节点，其中包括节点的值和指向下一个节点的指针。


class Node {
public:
  Node(double val) : m_val(val), m_next(nullptr) {}
  double m_val;
  Node *m_next;
};

然后定义一个栈类，表示栈的基本操作，包括入栈、出栈、取栈顶元素等操作。


class Stack {
public:
  bool isEmpty() const return m_top == nullptr;
  double top() const return m_top->m_val;
  void push(double val) {
    auto n = new Node(val);
    n->m_next = m_top;
    m_top = n;
  }
  double pop() {
    if (!isEmpty())
      auto val = m_top->m_val;
      auto tmp = m_top;
      m_top = m_top->m_next;
      delete tmp;
      return val;
    
    throw std::domain_error("stack underflow");
  }
private:
  Node *m_top = nullptr;
};

现在，我们使用上述定义好的栈类来实现表达式求值。具体的步骤如下：

1. 我们可以先定义一个栈，用来存储操作符和操作数。

2. 遍历表达式，对于每个操作数，将其入栈；对于每个操作符，从栈中取出两个操作数，通过该操作符计算得到一个中间结果，并将该结果入栈。

3. 遍历结束后，栈中只剩下一个元素，即表达式的计算结果。

代码如下：


double eval(const std::string &expr) {
  Stack stack;
  for (size_t i = 0; i < expr.length(); ++i) {
    if (isdigit(expr[i])) {
      auto val = expr[i] - '0';
      while (i + 1 < expr.length() && isdigit(expr[i + 1])) {
        val = val * 10 + (expr[++i] - '0');
      }
      stack.push(val);
    } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' ||
          expr[i] == '/') {
      auto op = expr[i];
      auto rhs = stack.pop();
      auto lhs = stack.pop();
      switch (op) {
      case '+':
        stack.push(lhs + rhs);
        break;
      case '-':
        stack.push(lhs - rhs);
        break;
      case '*':
        stack.push(lhs * rhs);
        break;
      case '/':
        stack.push(lhs / rhs);
        break;
      }
    }
  }
  if (!stack.isEmpty()) {
    return stack.pop();
  }
  throw std::invalid_argument("empty expression");
}

现在，我们可以使用上述的代码来计算任意的算术表达式了，例如：


std::cout << eval("2 + 3 * 4") << std::endl;   // Output: 14
std::cout << eval("(2 + 3) * 4 / 2 - 1") << std::endl; // Output: 8

总结来说，栈是一个简单而强大的数据结构，可应用于多种问题中。使用C++语言可以轻松实现栈数据结构，并使用它来解决表达式求值问题。对于开发人员来说，了解如何实现栈和使用它来解决实际问题都是非常有益的技能。

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

下一篇: "C++输入个人信息：姓名、籍贯、性别"

评论区

()

相似文章