中缀表达式转二叉树-创新互联

#includeusing namespace std;

using LL = long long;

class PBTNode {public:
	PBTNode* l;
	PBTNode* r;

	char op; //保持操作符,操作符为x时，表示数字类型
	LL num;  //保存数字

	PBTNode() {l = NULL;
		r = NULL;
	}
};

class PrefixBinaryTree {private:
	PBTNode* root;

	vectortoken_list;

	stack st; //符号栈
	vectorve; //后缀序列

	int pre_map[256];//符号优先级表

	//判断优先级
	int pre(char c) {return pre_map[c];
	}

	//字符串转整型
	LL string_to_num(string s) {stringstream ss(s);
		LL v;
		ss >>v;
		return v;
	}

	LL calc_dfs(PBTNode* p) {if(p->op == 'x') return p->num;
		
		LL a = calc_dfs(p->l);
		LL b = calc_dfs(p->r);

		if(p->op == '+') return a + b;
		if(p->op == '-') return a - b;
		if(p->op == '*') return a * b;
		if(p->op == '/') return a / b;

		return 0;
	}

public:
	PrefixBinaryTree() {memset(pre_map, 0, sizeof(pre_map));
		pre_map['+'] = 1;
		pre_map['-'] = 1;
		pre_map['*'] = 2;
		pre_map['/'] = 2;
	}

	//前缀表达式转换成token列表
	void to_token(string expr) {string str_t;
		int n = expr.length();
		int i = 0;

		while(i< n) {	char x = expr[i];
			if(x == ' ') {		i++;
			} else if(pre_map[x] >0 || x == '(' || x == ')') {		PBTNode* p = new PBTNode;
				p->op = x;
				token_list.push_back(p);
				i++;
			} else if(isdigit(x)) {		string str_t;
				char y = expr[i];
				while(isdigit(y)) {str_t.push_back(y);
					i++;
					y = expr[i];
				}
				PBTNode* p = new PBTNode;
				p->op  = 'x';
				p->num = string_to_num(str_t);
				token_list.push_back(p);
			}
		}
	}

	//打印token列表
	void print_token_list() {for(auto p : token_list) {	if(p->op == 'x') {		printf("[%lld]", p->num);
			} else {		printf("[%c]", p->op);
			}
		}
		printf("\n");
	}

	//前缀token列表转后缀序列
	void to_postfix() {for(auto p : token_list) {	if(p->op == 'x') {		ve.push_back(p);
			} else if(st.empty() || p->op == '(') {		st.push(p);
			} else if(p->op == ')') {		while(st.top()->op != '(') {ve.push_back(st.top());
					st.pop();
				}
				st.pop();//左括号出栈
			} else {		//确保符号C比栈下一个优先级高
				while(!st.empty() && pre(p->op)<= pre(st.top()->op)) {ve.push_back(st.top());
					st.pop();
				}
				st.push(p);
			}
		}

		while(!st.empty()) {	ve.push_back(st.top());
			st.pop();
		}
	}

	//得到后缀序列
	string get_postfix() {string buf;
		stringstream ss;
		for(auto p : ve) {	if(p->op == 'x') {		ss<< "["<< p->num<< "]";
			} else {		ss<< "["<< p->op<< "]";
			}
		}
		ss >>buf;
		return buf;
	}

	//创建表达式二叉树
	void build_tree() {stacksts;
		for(auto p : ve) {	if(p->op == 'x') {		p->l = NULL;
				p->r = NULL;
				sts.push(p);
			} else if(pre_map[p->op] >0) {		p->r = sts.top();
				sts.pop();

				p->l = sts.top();
				sts.pop();
				sts.push(p);
			}
		}
		root = sts.top();
	}

	//先序遍历
	void preorder(PBTNode* p) {if(p == NULL) return;
		if(p->op == 'x') {	cout<< "["<< p->num<< "]";
		} else {	cout<< "["<< p->op<< "]";
		}
		preorder(p->l);
		preorder(p->r);
	}

	//先序遍历打印
	void print_preorder() {printf("preorder:");
		preorder(root);
		printf("\n");
	}

	int calc() {return calc_dfs(root);
	}
};

int main() {PrefixBinaryTree x;
	string expr = "2*(36+5)+17/1-4";
	x.to_token(expr);
	x.to_postfix();
	x.build_tree();
	LL v = x.calc();
	
	x.print_token_list();
	string expr_postfix = x.get_postfix();
	cout<< expr_postfix<< endl;
	x.print_preorder();
	cout<< v<< endl;
	
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧