中缀表达式转二叉树-创新互联
标准算法
新闻名称:中缀表达式转二叉树-创新互联
本文来源:http://myzitong.com/article/hdijs.html
#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元起,快前往官网查看详情吧
成都创新互联公司主营日照网站建设的网络公司,主营网站建设方案,成都App定制开发,日照h5小程序定制开发搭建,日照网站营销推广欢迎日照等地区企业咨询新闻名称:中缀表达式转二叉树-创新互联
本文来源:http://myzitong.com/article/hdijs.html