//抽象语法树
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <stack>

using namespace std;

string str;
bool is_right = true;     //判断是否识别成功
char sym;                 //每次读入的字符
set<char> follow;

struct TreeNode{
    string val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(string s) : val(s), left(NULL), right(NULL) {}        //一个参数的构造函数
    TreeNode(string s, TreeNode* l, TreeNode* r) : val(s), left(l), right(r) {}  //多个参数的构造函数
};

int index;
TreeNode* Expr();
TreeNode* Expr1(TreeNode* arg1);
TreeNode* Term(TreeNode* arg1, TreeNode* op);
TreeNode* Term1(TreeNode* arg1);
TreeNode* Factor();
void error();
void init();
void postorder(TreeNode* root);
void inorder(TreeNode* root);

int main()
{
    init();
    //cin >> str;   //读入算术表达式
    str = "a+b*2/4-(a+b)*3#";       //"a+b*2/4-(a+b)*3#"
    sym = str[0];
    TreeNode* res = Expr();
    if(sym == '#' && is_right)
    {
        cout << "success" << endl;
        cout << "算术表达式抽象语法树的后序遍历结果是:   ";
        postorder(res);
        cout << endl;
        cout << "算术表达式抽象语法树的中序遍历结果是:   ";
        inorder(res);
    }
    else
        cout << "fail" << endl;
    return 0;
}

void init() {
    follow.insert('+');    //定义Term1的follow集
    follow.insert('-');
    follow.insert(')');
    follow.insert('#');
}

TreeNode* Expr() {
    TreeNode* s1 = new TreeNode("");
    TreeNode* term = Term(s1, s1);     //第一次传两个空节点进去
    TreeNode* expr1 = Expr1(term);
    return expr1;
}

TreeNode* Expr1(TreeNode* arg1) {
    if(sym == '+' || sym == '-')
    {
        string t = "";
        t += sym;
        TreeNode* op = new TreeNode(t);
        sym = str[++ index];
        TreeNode* term = Term(arg1, op);
        TreeNode* expr1 = Expr1(term);
        return expr1;
    }
    else if(sym != ')' && sym != '#')
    {
        error();
        return NULL;
    }
    else return arg1;
    return NULL;
}

TreeNode* Term(TreeNode* arg1, TreeNode* op) {     //传进来一个操作运算符和一个运算对象
    TreeNode* arg2 = Factor();
    if(sym == '*' || sym == '/')
    {
        TreeNode* term1 = Term1(arg2);
        TreeNode* res = new TreeNode(op->val, arg1, term1);
        return res;
    }
    else       //Term1产生为空，也就是sym是Term1的follow集
    {
        if(arg1->val.size())
        {
            TreeNode* res = new TreeNode(op->val, arg1, arg2);
            return res;
        }
        else return arg2;
    }
    return NULL;
}

TreeNode* Term1(TreeNode* arg1) {
    if(sym == '*' || sym == '/')
    {
        string op = "";
        op += sym;   //Term1产生的操作运算符
        sym = str[++ index];
        TreeNode* fact = Factor();   //返回的运算对象
        TreeNode* res = new TreeNode(op, arg1, fact);
        if(sym == '*' || sym == '/')  //后面还是*或者/
        {
            TreeNode* res1 = Term1(res);
            return res1;
        }
        else
        {
            return res;
        }
    }
    else if(follow.count(sym) == 0)  //+ - ) #，这些是Term1的follow集
    {
        error();
        return NULL;
    }
}

TreeNode* Factor() {
    if((sym >= 'a' && sym <= 'z') || (sym >= 'A' && sym <= 'Z') || (sym >= '0' && sym <= '9'))
       {
           string t = "";
           t += sym;
           sym = str[++ index];
           TreeNode* res = new TreeNode(t);
           return res;
       }
    else if(sym == '(')
    {
        sym = str[++ index];
        TreeNode* res = Expr();      //返回（）内的抽象语法树的根节点
        if(sym == ')') sym = str[++ index];
        else error();
        return res;
    }
    else
    {
        error();
        return NULL;
    }
}

void error() {
    is_right = false;
}

void postorder(TreeNode* root)
{
    if(root->left) postorder(root->left);
    if(root->right) postorder(root->right);
    cout << root->val;
}

void inorder(TreeNode* root)
{
    if(root->left) inorder(root->left);
    cout << root->val;
    if(root->right) inorder(root->right);
}

四元式
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <stack>

using namespace std;

string str;
bool is_right = true;     //判断是否识别成功
char ch;
set<char> follow;

struct quater{            //定义四元式
    string result;
    string arg1;
    string arg2;
    string op;
}quat[100];
int quat_index = 0;
void getQuat(string op, string arg1, string arg2, string result)
{
    quat[quat_index].op = op;
    quat[quat_index].arg1 = arg1;
    quat[quat_index].arg2 = arg2;
    quat[quat_index].result = result;
    quat_index ++;
}
int tI = 1;              //定义当前是t几了，比如t1,t2,t3;
string to_str(int a)     //整型转变为string型
{
    string s;
    while(a) s += '0' + a%10, a /= 10;
    return s;
}
string newT()            //创建临时变量
{
    int t = tI ++;
    return "t" + to_str(t);
}

int index;
string Expr();
string Expr1(string arg1);
string Term(string arg1, string op);
string Term1(string arg1);
string Factor();
void error();
void init();

int main()
{
    init();
    //cin >> str;   //读入算术表达式
    str = "a+((b-c)+2)*3#";    //a+b*2/4-(b+c)*3#
    ch = str[0];
    Expr();
    if(ch == '#' && is_right)
    {
        cout << "success" << endl;
        for(int i = 0; i < quat_index; i ++)
            cout << '(' << quat[i].op << ',' << quat[i].arg1 << ',' << quat[i].arg2 << ',' << quat[i].result << ')' << endl;
    }
    else
        cout << "fail" << endl;
    return 0;
}

void init() {
    follow.insert('+');    //定义Term1的follow集
    follow.insert('-');
    follow.insert(')');
    follow.insert('#');
}

string Expr() {
    string res, arg1;
    arg1 = Term("", "");
    res = Expr1(arg1);
    return res;
}

string Expr1(string arg1) {
    string res, arg2;
    if(ch == '+' || ch == '-')
    {
        string t = "";
        t += ch;
        ch = str[++ index];
        arg2 = Term(arg1, t);
        res = Expr1(arg2);
    }
    else if(ch != ')' && ch != '#')  //ch不在Expr1的follow集中
        error();
    else return arg1;
    return res;
}

string Term(string arg1, string op) {  //传递过来的属性是操作运算符+或者-，运算对象
    string res, arg2; 
    string arg3 = Factor();            //Factor产生的字符
    if(ch == '*' || ch == '/')         //Term1非空
    {
        res = newT();                  //返回的中间变量
        arg2 = Term1(arg3); 
        getQuat(op, arg1, arg2, res);
    }
    else                               //Term1不考虑错误，为空
    {
        if(arg1.size())                //传进来的arg1不是""
        {
            res = newT();
            getQuat(op, arg1, arg3, res);
        }
        else return arg3; 
    }
    return res;
}

string Term1(string arg1) {
    string res, arg2;
    if(ch == '*' || ch == '/')
    {
        string t = newT();
        string op = "";
        op += ch;                     //记录操作运算符
        ch = str[++ index];
        arg2 = Factor();
        getQuat(op, arg1, arg2, t);   //t是中间变量
        if(ch == '*' || ch == '/')    //非空
            res = Term1(t);
        else 
        {
            return t;
        }
    }
    else if(follow.count(ch) > 0)   //ch是Term1的follow集
    {
        return res;
    }
    else if(follow.count(ch) == 0)  //ch不在Term1的follow集 + - ) #, 一定出现错误
       error();
    return res;
}

string Factor() {
    string res = "";
    if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))
       {
           res += ch;
           ch = str[++ index];
           return res;
       }
    else if(ch == '(')
    {
        ch = str[++ index];
        res += Expr();
        if(ch == ')') ch = str[++ index];
        else error();
    }
    else error();
    return res;
}

void error() {
    is_right = false;
}