首页 > 代码库 > 前缀转后缀（表达式）
前缀转后缀（表达式）
问题描述：
前缀表达式转成后缀表达式，示例：
* + 4 2 + 3 6 => 4 2 + 3 6 + *
思路（树）：
1. 从左往右扫描串
2. 遇到操作符则递归构造树节点，当前操作符是根节点，并递归构造左右子节点
3. 后序遍历当前结果，并返回
代码：
1 #include <string> 2 #include <sstream> 3 #include <iostream> 4 5 using namespace std; 6 7 string input_str = "* + 4.3 2 + 3.5 6.2"; 8 int ind = 0; 9 10 //树结构11 typedef struct BinaryTreeNode12 {13 string cur_str;14 BinaryTreeNode *left;15 BinaryTreeNode *right;16 BinaryTreeNode(string _cur_str)17 {18 cur_str = _cur_str;19 left = NULL;20 right = NULL;21 }22 } BNode_t;23 24 //后序遍历树25 void post_traverse(BNode_t *root, string &post_str)26 {27 if( root == NULL )28 return;29 post_traverse(root->left, post_str);30 post_traverse(root->right, post_str);31 if( post_str != "" )32 post_str += " " + root->cur_str;33 else34 post_str = root->cur_str;35 }36 37 //得到下一个38 string get_next()39 {40 string next = "";41 for(; ind < input_str.size(); ind++)42 {43 if( input_str[ind] != ‘ ‘ )44 next += input_str[ind];45 else46 break;47 }48 ind++;49 return next;50 }51 52 //转换：递归构造树，并后序遍历53 string transform()54 {55 string post_str;56 string next = get_next();57 if( ! isdigit(next[0]) )58 {59 BNode_t *root = new BNode_t(next);60 root->left = new BNode_t( transform() );61 root->right = new BNode_t( transform() );62 post_traverse(root, post_str);63 delete root->left;64 delete root->right;65 delete root;66 return post_str;67 }68 else return next;69 }70 71 72 int main()73 {74 cout << transform() << endl;75 return 0;76 }
转载请注明引用自：
http://www.cnblogs.com/breakthings/p/4053444.html
前缀转后缀（表达式）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。