C++简单算术表达式求值 |21xrx.com

C++简单算术表达式求值

2023-07-08 13:14:20 深夜i -- --

C++ 算术表达式求值

在编程中，算术表达式求值是一个重要的操作，实现它可以帮助我们进行数值计算、数据分析等各种任务。C++是一种广泛使用的编程语言，它提供了多种算术表达式求值的方法，其中包括简单算术表达式求值。

简单算术表达式是指只包含加、减、乘、除、乘方和取模六种运算符的表达式。C++提供了多种方法进行简单算术表达式求值，包括使用程序逐个字符解析表达式、使用栈进行求值、使用递归等方法。本篇文章将介绍基于栈的方法。

基于栈的简单算术表达式求值方法分为两个步骤：表达式转换和求值。表达式转换是将原始表达式转换为后缀表达式，后缀表达式是指将运算符放在操作数之后的有效表达式。例如，表达式“3+4*2/(1-5)^2”的后缀表达式为“3 4 2 * 1 5 - 2 ^ / +”。求值是在后缀表达式上进行的。基于栈的算法可以轻松地进行表达式转换和求值。

表达式转换需要使用运算符栈和结果队列。遍历原始表达式中的每个字符，如果它是一个数字，则将其添加到结果队列中；如果是一个运算符，则将其与运算符栈中的运算符进行比较，确定是否需要弹出一个运算符并将其添加到结果队列中。该过程一直进行到表达式的末尾。最后，将运算符栈中的所有运算符依次弹出并添加到结果队列中，生成后缀表达式。

求值需要使用操作数栈。遍历后缀表达式中的每个字符，如果它是一个数字，则将其添加到操作数栈中；如果是一个运算符，则从操作数栈中弹出两个操作数，应用运算符，并将结果添加回操作数栈中。该过程一直进行到后缀表达式的末尾。最终，操作数栈中的唯一元素就是表达式的值。

C++提供了多个库可以用于实现基于栈的简单算术表达式求值方法。例如，可以使用STL中的std::stack和std::queue容器实现运算符栈和结果队列，同时使用函数递归进行表达式转换和求值。代码示例如下：


#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
queue<string> shuntingYard(string expr) {
  queue<string> output;
  stack<char> opStack;
  for (int i = 0; i < expr.size(); ++i) {
    char ch = expr[i];
    if (isdigit(ch)) {
      int num = ch - '0';
      while (i+1 < expr.size() && isdigit(expr[i+1])) {
        num = num * 10 + (expr[i+1] - '0');
        i++;
      }
      output.push(to_string(num));
    }
    else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '^') {
      while (!opStack.empty() && opStack.top() != '(' &&
          ((ch == '*' || ch == '/' || ch == '%') || (ch == '+' || ch == '-') || (ch == '^' && opStack.top() == '^' && !opStack.empty())) && opStack.top() != '!') {
        char op = opStack.top();
        opStack.pop();
        output.push(string(1, op));
      }
      opStack.push(ch);
    }
    else if (ch == '(') {
      opStack.push(ch);
    }
    else if (ch == ')') {
      while (!opStack.empty() && opStack.top() != '(') {
        char op = opStack.top();
        opStack.pop();
        if (op != '!') {
          output.push(string(1, op));
        }
      }
      if (!opStack.empty()) {
        opStack.pop();
      }
      else {
        opStack.push('!');
      }
    }
  }
  while (!opStack.empty()) {
    char op = opStack.top();
    opStack.pop();
    if (op != '(' && op != ')') {
      output.push(string(1, op));
    }
  }
  return output;
}
double evaluate(queue<string> expr) {
  stack<double> nums;
  while (!expr.empty()) {
    string token = expr.front();
    expr.pop();
    if (isdigit(token[0])) {
      nums.push(stod(token));
    }
    else {
      double right = nums.top();
      nums.pop();
      double left = nums.top();
      nums.pop();
      if (token == "+") {
        nums.push(left + right);
      }
      else if (token == "-") {
        nums.push(left - right);
      }
      else if (token == "*") {
        nums.push(left * right);
      }
      else if (token == "/") {
        nums.push(left / right);
      }
      else if (token == "%") {
        nums.push(fmod(left, right));
      }
      else if (token == "^") {
        nums.push(pow(left, right));
      }
    }
  }
  return nums.top();
}
int main() {
  string expr = "3+4*2/(1-5)^2";
  queue<string> postFixExpr = shuntingYard(expr);
  double result = evaluate(postFixExpr);
  cout << result << endl;
  return 0;
}

总之，C++提供了多种简单算术表达式求解方法，其中基于栈的方法是一种流行的技术。如果你需要进行数值计算或数据分析，应尝试使用C++进行算术表达式求值。

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

下一篇: C++在图论中的应用

评论区

()

相似文章