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

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

2023-06-23 18:30:18 深夜i 13 0

C++ 栈表达式求值实现

C++是一种高级编程语言，可以用来实现各种应用程序和系统。其中，使用C++实现栈来求解表达式的值，是一种常见的程序设计方法。栈是一种数据结构，具有后进先出（LIFO）的特性。在表达式求值的过程中，我们可以利用栈来存储和计算操作数和操作符，从而得到最终的表达式结果。

表达式求值是计算机程序设计中的重要问题之一，它涉及到算术运算、逻辑运算等多个方面。在C++程序中，可以用栈来实现表达式求值。具体来说，我们可以将表达式中的操作数和操作符依次压入栈中，在计算过程中依次弹出和计算，最终得到表达式的值。

在实现中，我们需要定义一个栈的结构体或类，并为其定义一些基本的操作，如压栈、弹栈、取栈顶等。同时，我们需要解析表达式，并将其转换成一个栈，栈的每个元素代表表达式中的一个操作数或操作符。接下来，我们可以按照逆波兰表达式的方式依次弹出栈中的元素，并计算表达式的值。

下面是一个简单的C++代码示例，展示了如何用栈实现表达式求值：

#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 定义操作符优先级
int priority(char op) {
  if (op == '+' || op == '-') return 1;
  if (op == '*' || op == '/') return 2;
  return 0;
}
int main() {
  string expression;
  getline(cin, expression);  // 读取表达式
  stack<int> nums;    // 定义操作数栈
  stack<char> ops;    // 定义操作符栈
  for (int i = 0; i < expression.length(); i++) {
    char ch = expression[i];
    if (ch == ' ') continue;  // 忽略空格
    if (isdigit(ch)) {
      int num = ch - '0';
      while (i+1 < expression.length() && isdigit(expression[i+1])) {
        num = num*10 + expression[i+1] - '0';
        i++;
      }
      nums.push(num);   // 压入操作数栈
    }
    else if (ch == '(') {
      ops.push(ch);    // 压入操作符栈
    }
    else if (ch == ')') {
      while (ops.top() != '(') {
        // 弹出操作符栈并计算
        int num2 = nums.top(); nums.pop();
        int num1 = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        if (op == '+') nums.push(num1 + num2);
        else if (op == '-') nums.push(num1 - num2);
        else if (op == '*') nums.push(num1 * num2);
        else if (op == '/') nums.push(num1 / num2);
      }
      ops.pop();   // 弹出左括号
    }
    else {
      while (!ops.empty() && priority(ch) <= priority(ops.top())) {
        // 弹出操作符栈并计算
        int num2 = nums.top(); nums.pop();
        int num1 = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        if (op == '+') nums.push(num1 + num2);
        else if (op == '-') nums.push(num1 - num2);
        else if (op == '*') nums.push(num1 * num2);
        else if (op == '/') nums.push(num1 / num2);
      }
      ops.push(ch);  // 压入操作符栈
    }
  }
  while (!ops.empty()) {
    // 弹出操作符栈并计算
    int num2 = nums.top(); nums.pop();
    int num1 = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();
    if (op == '+') nums.push(num1 + num2);
    else if (op == '-') nums.push(num1 - num2);
    else if (op == '*') nums.push(num1 * num2);
    else if (op == '/') nums.push(num1 / num2);
  }
  // 输出表达式结果
  cout << nums.top() << endl;
  return 0;
}

在上面的示例代码中，我们首先读取用户输入的表达式，并定义了操作数栈和操作符栈。然后，我们按照逆波兰表达式的方式依次遍历表达式中的每个字符，将操作数压入操作数栈，将操作符压入操作符栈，并根据不同的情况进行计算。待整个表达式计算完毕后，我们可以从操作数栈中弹出最终结果，并输出到屏幕上。

总的来说，C++中使用栈实现表达式求值是一种非常常用的编程技巧。通过这种方法，我们可以快速、高效地计算各种表达式的值，为程序设计和计算机科学领域提供了重要的支持和帮助。

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

下一篇: C++矩阵计算器

评论区

相似文章