算术表达式前缀表达式,后缀表达式计算结果

简单的前缀表达式计算

简单是指表达式简单，所有数字均为 0~9 之间，不是代码简单

【关于二叉树的递归创建与非递归遍历】
【其他：中缀表达式转后缀表达式】
【其他：后缀表达式计算】

思路

因为给定的是前缀表达式，那么方便我们直接递归地建一颗表达式树，并且递归地计算

递归创建步骤：

读取字符如果字符是数字，那么说明是叶子节点，直接将当前节点赋值为数字如果字符是符号，说明是某个根节点，不仅需要保存当前节点的符号，还需要递归地对当前节点的左右子节点创建树

递归计算步骤：

如果当前节点存储的值是数字，说明是叶子节点，直接返回该数字如果当前节点存储的是符号，说明是某个根节点，需要递归地计算左右子树的值 l, r，然后再运算： l 运算符 r 的值 代码

#include <iostream>using namespace std;class node{public:node();node* lchild;node* rchild;char data;};node::node(){this->lchild = NULL;this->rchild = NULL;}// 递归创建表达式树void creat(node*& t){char c;cin>>c;if('0'<=c && c<='9'){node* nd = new node();nd->data = c;t = nd;}else{node* nd = new node();nd->data = c;t = nd;creat(t->lchild);creat(t->rchild);}}// 递归计算表达式树的值#define char2int(c) ((int)(c - '0'))int count(node* t){char c = t->data;if('0'<=c && c<='9'){return char2int(c);}else{int l = count(t->lchild);int r = count(t->rchild);if(c == '+'){return (l + r);}if(c == '-'){return (l - r);}if(c == '*'){return (l * r);}if(c == '/'){return (l / r);}}}int main(){node* t;creat(t);cout<<count(t)<<endl;return 0;}