2013
12-23

# Expressions

Have you taken the course named Data Structure? Did you pass it? If you do, you should know that a mathematical expression can be expressed as a tree and why. In this problem, you are given some expressions, and you are supposed to draw the tree.

The expressions are composed of these letters:
(1) ‘a’, ‘b’, …, ‘z’ : means an operand;
(2) ‘+’, ‘-’, ‘*’, ‘/’ : dyadic operator, means plus sign, subtraction sign, multiplication sign and division sign;
(3) ‘-’ : monadic operator, means negative sign;
(4) ‘(‘, ‘)’ : used in pairs to alter priority.

Input consists of multiple expressions each on a line (not exceed 50 letters). You should proceed to the end of file.

For each expression, You should draw a tree that can express it, following the styles indicated in the sample output.

Note that the ‘#’ in the sample are supposed to tell you that there are spaces at the back of some lines, and you should ignore it in your output.

a+b+c
(a-a)*b+(-c)

   + #
+  c#
a b  #
+  #
*  - #
-  b  c#
a a     #

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cctype>
using namespace std;

struct node
{
char data;
node* left,*right;
node(char d=0,node*l=0,node*r=0):data(d),left(l),right(r){}
};

node *build(char data,node* left,node* right)
{
node*father=new node(data,left,right);
return father;
}

int main()
{
string s;
int cas;
cin>>cas;
while(cas--)
{
cin>>s;
stack<node*>stck;
queue<node*>que;
string ans;
for(size_t i=0;i!=s.size();i++)
{
if(islower(s[i]))
{
node* tree=new node(s[i],0,0);
stck.push(tree);
}
else
{
node* r=stck.top();stck.pop();
node* l=stck.top();stck.pop();
stck.push(build(s[i],l,r));
}
}
que.push(stck.top());
while(!que.empty())
{
node* cur=que.front();que.pop();
ans+=cur->data;
if(cur->left)que.push(cur->left);
if(cur->right)que.push(cur->right);
}
for(int i=ans.size()-1;i>-1;i--)
cout<<ans[i];
cout<<endl;
}
return 0;
}

,