如何在构造了加减乘除的二叉树的基础上
构造加上neg(取反）和doubleMe（平方）的二叉树来输出中缀表达式和前缀求值
要能完成输入这个式子add(sub(neg(4),12),muti(doubleMe(2),5))
最后输出(（-4） -12) + （(2 ^ 2） * 5) = 4
基础代码
//二叉树结构体
struct TreeNode {
string data;//数据域
TreeNode* left;//左子树
TreeNode* right;//右子树
TreeNode(const string& val) :data(val), left(nullptr), right(nullptr) //构造函数
{
}
};
//定义操作符优先级映射
map<string, int> PriMap = {
{"+",3},
{"-",3},
{"*",7},
{"/",7},
};
string ToInfix(TreeNode* root) { //nullptr为指针空值
if (root == nullptr) { //判断根是否为空
return ""; //否则进入死循环
}
else
{
string infix = "";
string leftExpr = ToInfix(root->left);
string rightExpr = ToInfix(root->right);
//根据操作符优先级判断是否需要添加左括号
if (root->left != nullptr && PriMap.count(root->left->data) != 0 &&
PriMap[root->data] >= PriMap[root->left->data]) {
infix += "(" + leftExpr + ")";
}
else {
infix += leftExpr;
}
//添加根结点
infix += root->data;
//根据操作符优先级判断是否需要添加右括号
if (root->right != nullptr && PriMap.count(root->right->data) != 0 &&
PriMap[root->data] >= PriMap[root->right->data]) {
infix += "(" + rightExpr + ")";
}
else {
infix += rightExpr;
}
return infix;
}
}
//构造二叉树
TreeNode* buildBinaryTree(vector<string>& tokens, int& index) {
string token = tokens[index++];
if (token == "+" || token == "-" || token == "*" || token == "/") {
TreeNode* node = new TreeNode(token);
node->left = buildBinaryTree(tokens, index); //通过递归构造二叉树
node->right = buildBinaryTree(tokens, index);
return node; //返回链表头指针
}
else {
return new TreeNode(token);
}
}
#include <iostream>
#include <string>
#include <stack>
using namespace std;
// 节点结构体
struct TreeNode {
string data; // 存储运算符或操作数
TreeNode* left; // 左子树指针
TreeNode* right; // 右子树指针
// 构造函数
TreeNode(string value): data(value), left(nullptr), right(nullptr) {}
};
// 取反操作
string negate(string value) {
return "(0 - " + value + ")";
}
// 平方操作
string square(string value) {
return "(" + value + " ^ 2)";
}
// 判断字符是否为运算符
bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
// 构建表达式的二叉树
TreeNode* buildExpressionTree(string expression) {
stack<TreeNode*> stack; // 使用栈来构建二叉树
for (int i = 0; i < expression.length(); i++) {
if (isdigit(expression[i])) { // 如果是数字则作为操作数创建节点
string operand;
while (isdigit(expression[i])) {
operand += expression[i];
i++;
}
stack.push(new TreeNode(operand));
i--;
} else if (expression[i] == '(') { // 如果是左括号则继续下一个字符
continue;
} else if (isOperator(expression[i])) { // 如果是运算符
TreeNode* node = new TreeNode(string(1, expression[i])); // 创建节点
node->right = stack.top(); // 设置右子树
stack.pop();
node->left = stack.top(); // 设置左子树
stack.pop();
stack.push(node); // 将新节点压入栈中
} else if (expression[i] == ')') { // 如果是右括号
continue;
} else { // 其他情况则是操作符需要添加
string operation;
while (expression[i] != '(') {
operation += expression[i];
i++;
}
stack.top()->data = operation + "(" + stack.top()->data + ")"; // 在操作数前面添加操作符
i--;
}
}
return stack.top(); // 返回根节点
}
// 中序遍历输出中缀表达式
void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left); // 遍历左子树
cout << root->data << " "; // 输出节点数据
inorderTraversal(root->right); // 遍历右子树
}
}
// 前序遍历求值
double evaluatePreorder(TreeNode* root) {
if (root != nullptr) {
if (isdigit(root->data[0])) { // 如果是操作数则转为double类型并返回
return stod(root->data);
} else { // 如果是操作符则进行相应的操作
if (root->data == "+") {
return evaluatePreorder(root->left) + evaluatePreorder(root->right);
} else if (root->data == "-") {
return evaluatePreorder(root->left) - evaluatePreorder(root->right);
} else if (root->data == "*") {
return evaluatePreorder(root->left) * evaluatePreorder(root->right);
} else if (root->data == "/") {
return evaluatePreorder(root->left) / evaluatePreorder(root->right);
} else if (root->data == "^") {
return pow(evaluatePreorder(root->left), evaluatePreorder(root->right));
}
}
}
return 0; // 如果树为空则返回0
}
int main() {
string expression = "add(sub(neg(4),12),muti(doubleMe(2),5))";
TreeNode* root = buildExpressionTree(expression);
inorderTraversal(root);
double result = evaluatePreorder(root);
cout << "= " << result << endl;
return 0;
}
这段代码实现了根据输入的表达式构建二叉树，并输出中缀表达式和前缀求值的功能。在代码中，将取反操作和平方操作都分别封装为了相应的函数。通过遍历表达式字符串，使用栈来构建二叉树，并根据运算符的优先级来确定操作数的位置。最后，通过中序遍历输出中缀表达式，通过前序遍历求值来计算表达式的结果。最终结果会输出到屏幕上。