首页 > 搜索 > BFS搜索 > HDU 1855 Expressions-栈-[解题报告] C++
2013
12-23

HDU 1855 Expressions-栈-[解题报告] C++

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;
}

解题报告转自:http://blog.csdn.net/ultimater/article/details/8015040


,