您现在的位置是：首页 >技术杂谈 >【算法练习】深度优先搜索算法(DFS) 实现 利用诱导公式化简含三角函数的表达式网站首页技术杂谈

创作背景

高二假期啦！正在进行一轮复习。
正好复习到三角函数，遂获灵感，作文以记之。

项目需求

利用诱导公式，化简含三角函数的表达式。
①先判断输入表达式是否合法；
②若表达式合法，则进行化简；
③要求能处理嵌套结构，如：
“sin(5pi/2 + cos(3pi/2 - tan(pi + 8)))”

附：基本的三角函数诱导公式：

公式一：
设α为任意角，终边相同的角的同一三角函数的值相等：
sin（2kπ＋α）＝sinα （k∈Z）
cos（2kπ＋α）＝cosα （k∈Z）
tan（2kπ＋α）＝tanα （k∈Z）

公式二：
设α为任意角，π+α的三角函数值与α的三角函数值之间的关系：
sin（π＋α）＝－sinα
cos（π＋α）＝－cosα
tan（π＋α）＝tanα

公式三：
任意角α与 -α的三角函数值之间的关系：
sin（－α）＝－sinα
cos（－α）＝cosα
tan（－α）＝－tanα

公式四：
利用公式二和公式三可以得到π-α与α的三角函数值之间的关系：
sin（π－α）＝sinα
cos（π－α）＝－cosα
tan（π－α）＝－tanα

公式五：
利用公式一和公式三可以得到2π-α与α的三角函数值之间的关系：
sin（2π－α）＝－sinα
cos（2π－α）＝cosα
tan（2π－α）＝－tanα

公式六：
π/2±α及3π/2±α与α的三角函数值之间的关系：
sin（π/2＋α）＝cosα
cos（π/2＋α）＝－sinα
tan（π/2＋α）＝－cotα

sin（π/2－α）＝cosα
cos（π/2－α）＝sinα
tan（π/2－α）＝cotα

sin（3π/2＋α）＝－cosα
cos（3π/2＋α）＝sinα
tan（3π/2＋α）＝－cotα

sin（3π/2－α）＝－cosα
cos（3π/2－α）＝－sinα
tan（3π/2－α）＝cotα

(以上k∈Z)

实现

环境

Windows 11 + Vscode + cmake
GCC(13.2.0)

算法流程

示例：

Input:  "sin(5*pi/2 + cos(3*pi/2 - tan(pi + 8)))"
处理流程：
1. 系数化简：
   5pi/2 → pi/2
   3pi/2 → 3pi/2
2. 处理最内层tan(pi+8) → tan(8)
3. 处理cos(3pi/2 - tan8) → -sin(tan8)
4. 处理sin(pi/2 + (-sin(tan8))) → cos(-sin(tan8)) → cos(sin(tan8))
Output: "cos(sin(tan(8)))"

项目结构

SIMPLIFICATION_V_1.0.0
├─build
├─include
│  └─InputFilter.h
├─src
│  ├─Filter
│  │  └─InputFilter.cpp
│  └─main.cpp
└─CMakeLists.txt

代码实现

//CMakeLists.txt
cmake_minimum_required(VERSION 3.5.0)
project(Simplification VERSION 1.0.0 LANGUAGES C CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED TRUE)

include_directories(${CMAKE_SOURCE_DIR}/include)

add_executable(${PROJECT_NAME} src/main.cpp src/Filter/InputFilter.cpp)

//InputFilter.h
#ifndef INPUTFILTER_H
#define INPUTFILTER_H
#include <string>
class InputFilter {
public:
  InputFilter();
  static bool isInputValid(std::string);
  static std::string simplification(std::string);
  ~InputFilter();
};
#endif // INPUTFILTER_H

//InputFilter.cpp
#include "InputFilter.h"
#include <stack>
#include <string>
#include <cctype>
#include <regex>

//判断输入表达式是否合法
bool InputFilter::isInputValid(std::string str) {
  std::stack<char> stack;
  std::string validFunctions[] = {"sin", "cos", "tan", "ln", "exp"};
  size_t i = 0;
  bool expectOperator = false;

  while (i < str.length()) {
      char c = str[i];

      if (c == '(' || c == '[' || c == '{') {
          stack.push(c);
          expectOperator = false;
      } else if (c == ')' || c == ']' || c == '}') {
          if (stack.empty()) {
              return false;
          }
          char top = stack.top();
          stack.pop();
          if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
              return false;
          }
          expectOperator = true;
      } else if (std::isalpha(c)) {
          bool validFunction = false;
          for (const auto &func : validFunctions) {
              if (str.substr(i, func.length()) == func) {
                  i += func.length();
                  if (i >= str.length() || str[i] != '(') {
                      return false; // 函数符号后面必须紧跟'('
                  }
                  stack.push('('); // '('入栈
                  validFunction = true;

                  // tan(pi/2) or tan(-pi/2) or tan(k*pi/2)等因定义域问题不合法的表达式
                  if (func == "tan") {
                      size_t j = i + 1; // 跳过'('
                      int piCount = 0;
                      bool isNegative = false;
                      bool hasPi = false;
                      bool hasOther = false;

                      while (j < str.length() && str[j] != ')') {
                          if (str[j] == 'p' && str.substr(j, 2) == "pi") {
                              piCount++;
                              hasPi = true;
                              j += 2;
                          } else if (str[j] == '-') {
                              isNegative = !isNegative;
                              j++;
                          } else if (std::isdigit(str[j])) {
                              j++;
                          } else if (str[j] == '+' || str[j] == '-' || str[j] == '*' || str[j] == '/' || str[j] == '%' || str[j] == '^') {
                              hasOther = true;
                              j++;
                          } else {
                              j++;
                          }
                      }

                      if (hasPi && !hasOther && (piCount % 2 == 1) && !isNegative) {
                          return false; // tan(pi/2) or tan(3*pi/2) or tan(k*pi/2)
                      }
                  }

                  break;
              }
          }
          if (!validFunction) {
              if (str.substr(i, 2) == "pi") {
                  i += 1; // 跳过“pi”
              } else {
                  return false;
              }
          }
          expectOperator = true;
      } else if (std::isdigit(c) || c == '.') {
          if (c == '.' && (i == 0 || !std::isdigit(str[i - 1]) || (i + 1 < str.length() && !std::isdigit(str[i + 1])))) {
              return false;
          }
          expectOperator = true;
      } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^') {
          if (!expectOperator && c != '-') {
              return false;
          }
          expectOperator = false;
      } else if (!std::isspace(c)) {
          return false;
      }
      i++;
  }

  return stack.empty() && expectOperator;
}

std::string InputFilter::simplification(std::string expr) {
  using namespace std;
  // ========================
  // 一、替换规则定义（优先级排序）
  // ========================
  vector<pair<regex, string>> rules = {
      /* 规则设计思路：
           1. 先处理大周期项（2π）
           2. 处理中等周期项（π）
           3. 处理特殊角度（π/2, 3π/2）
           4. 最后处理符号变化 */

      // [规则1] 处理2π周期项（最高优先级）
      // 匹配形式：三角函数(表达式 + 2π) 或 三角函数(2π + 表达式)
      {regex(R"((sin|cos|tan)(s*([^()]+)s*+s*2pis*([^()]*)s*))",
             regex::icase),
       "$1($2$3)"}, // 移除2π项

      // [规则2] 处理π加减法
      {regex(R"(sin(s*pis*+s*([^)]+)))", regex::icase),
       "-sin($1)"}, // sin(π + x) → -sin(x)
      {regex(R"(cos(s*pis*+s*([^)]+)))", regex::icase),
       "-cos($1)"}, // cos(π + x) → -cos(x)
      {regex(R"(tan(s*pis*+s*([^)]+)))", regex::icase),
       "tan($1)"}, // tan(π + x) → tan(x)（利用tan的π周期性）

      // [规则3] 处理π/2加减法（包含两种顺序）
      // 匹配形式：pi/2 ± x 或 x ± pi/2
      {regex(
           R"(sin(s*((pi/2s*[+-]s*([^()]+))|(([^()]+)s*[+-]s*pi/2))s*))",
           regex::icase),
       "cos($3$5)"}, // sin(π/2±x)=cos(x)
      {regex(
           R"(cos(s*((pi/2s*[+-]s*([^()]+))|(([^()]+)s*[+-]s*pi/2))s*))",
           regex::icase),
       "-sin($3$5)"}, // cos(π/2±x)=∓sin(x)
      {regex(
           R"(tan(s*((pi/2s*[+-]s*([^()]+))|(([^()]+)s*[+-]s*pi/2))s*))",
           regex::icase),
       "-cot($3$5)"}, // tan(π/2±x)=∓cot(x)

      // [规则4] 处理3π/2加减法（包含两种顺序）
      {regex(R"(sin(s*3pi/2s*+s*([^)]+)))", regex::icase),
       "-cos($1)"}, // sin(3π/2+x)=-cos(x)
      {regex(R"(sin(s*3pi/2s*-s*([^)]+)))", regex::icase),
       "-cos($1)"}, // sin(3π/2-x)=-cos(x)
      {regex(R"(cos(s*3pi/2s*+s*([^)]+)))", regex::icase),
       "sin($1)"}, // cos(3π/2+x)=sin(x)
      {regex(R"(cos(s*3pi/2s*-s*([^)]+)))", regex::icase),
       "-sin($1)"}, // cos(3π/2-x)=-sin(x)
      {regex(R"(tan(s*3pi/2s*+s*([^)]+)))", regex::icase),
       "-cot($1)"}, // tan(3π/2+x)=-cot(x)
      {regex(R"(tan(s*3pi/2s*-s*([^)]+)))", regex::icase),
       "cot($1)"} // tan(3π/2-x)=cot(x)
  };

  // ========================
  // 二、系数化简阶段
  // ========================
  /* 目标：将表达式中的数字*pi/2转换为标准形式
     例如：5pi/2 → pi/2 (因为5%4=1)
          6pi/2 → pi   (因为6%4=2)
          7pi/2 → 3pi/2 */
  regex coefficient_pattern(R"((d+)s**?s*pis*/s*2)");
  smatch match;
  string::const_iterator search_start(expr.cbegin());

  // 循环处理所有匹配项
  while (regex_search(search_start, expr.cend(), match, coefficient_pattern)) {
      int k = stoi(match[1]); // 提取系数
      int remainder = k % 4;  // 计算模4余数

      // 根据余数确定替换形式
      string replacement;
      switch (remainder) {
      case 0: replacement = "0"; break;     // 4nπ/2 = 2nπ → 0
      case 1: replacement = "pi/2"; break;  // (4n+1)π/2
      case 2: replacement = "pi"; break;    // (4n+2)π/2 = (2n+1)π → π
      case 3: replacement = "3pi/2"; break; // (4n+3)π/2
      }

      // 执行替换并更新搜索起点
      expr.replace(match.position(0), match.length(0), replacement);
      search_start = expr.cbegin() + match.position(0) + replacement.length();
  }

  // ========================
  // 三、递归处理嵌套结构
  // ========================
  /* 算法策略：
     1. 使用深度优先搜索(DFS)
     2. 优先处理最内层函数
     3. 循环直到无更多变化 */
  regex func_pattern(R"((sin|cos|tan)((.*?)))", regex::icase);
  bool changed;
  do {
      changed = false;
      string buffer = expr; // 保存当前表达式状态
      smatch match;

      // 阶段1：优先处理最内层函数（无嵌套）
      // 示例：优先处理cos(3pi/2)而不是外层的sin(...)
      while (regex_search(buffer, match, func_pattern)) {
          string full_match = match.str(); // 完整匹配项，如"sin(pi/2+x)"
          string func_name = match[1];     // 函数名：sin/cos/tan
          string arguments = match[2];     // 参数部分：如"pi/2+x"

          // 对参数进行逐步化简
          string simplified_args = arguments;
          for (auto &rule : rules) {
              simplified_args = regex_replace(simplified_args, rule.first, rule.second);
          }

          // 构造替换后的表达式
          string replacement = func_name + "(" + simplified_args + ")";
          if (replacement != full_match) {
              // 查找并替换原始表达式中的匹配项
              expr.replace(expr.find(full_match), full_match.length(), replacement);
              changed = true; // 标记有变化
          }
          buffer = match.suffix().str(); // 继续处理后续内容
      }

      // 阶段2：全局应用规则（处理可能的新产生项）
      for (auto &rule : rules) {
          expr = regex_replace(expr, rule.first, rule.second);
      }

  } while (changed); // 只要本轮有变化就继续循环，直到无变化为止

  return expr;
}

//main.cpp
#include "InputFilter.h"
#include <iostream>
#include <string>
using namespace std;
int main() {
  string input;
  cin >> input;
  int times = 0;
  //输入词数达100次 或 输入“exit”时推出
  while (times < 100 && input != "exit") {
      if (InputFilter::isInputValid(input)) {
          cout << "Valid!" << endl
               << "Before Simplification:" << input << endl;
          string simplified = InputFilter::simplification(input);
          cout << "After Simplification:" << simplified << endl;
      } else {
          cout << "Invalid!" << endl;
      }
      cin >> input;
      times++;
  }
}

分析与总结

本项目使用正则表达式匹配处理字符串，并结合深度优先搜索算法，递归处理嵌套结构。可以实现多数含三角函数表达式的初步化简。但仍有不足之处：
①负系数处理缺失：
目前的正则表达式(d+)只能匹配正整数，无法处理负系数（如-3pi/2）
②复杂表达式支持不足：
无法处理包含其他运算的复杂参数（如sin(2x + pi/2)）
③函数组合处理缺失：
无法处理cot等派生函数
④符号简化不足：
结果中可能保留冗余符号（如sin(-(x))而不是-sin(x)）*

上述问题，尚未有改进思路。欢迎各位大佬在评论区指点【抱拳】【抱拳】【抱拳】
需要源码，欢迎私信交流！

本人李某，专注原创，转载请注明！