若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1181: Treequivalence

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,352

题目描述

Treequivalence
The following grammar describes a textual notation for a tree with (not necessarily unique) vertex labels:

tree ::= label
tree ::= label ( subtrees )
subtrees ::= tree
subtrees ::= subtrees , tree
label ::= A | B | C | … | Z

That is, the representation of a tree consists of a label (which is an uppercase letter) or a label followed by a bracketed ordered list of trees separated by commas.
In order to draw such a tree on paper, we must write each label on the page, such that the labels for the subtrees of a vertex are positioned counter-clockwise about the vertex. The labels must be positioned such that non-intersecting line segments connect each vertex to each of its subtrees. That is to say, we draw the normal planar representation of the tree, preserving the order of subtrees. Beyond these constraints, the position, shape, and size of the representation is arbitrary.
For example, a possible graphical representation for A(B(C,D),E) is .
Given the textual representation for two trees, you are to determine whether or not they are equivalent. That is, do they share a common paper representation?
The first line of input contains t, the number of test cases. Each test case consists of two lines, each specifying a tree in the notation described above. Each line will contain at most 200 characters, and no white space. For each test case, output a line containing "same" or "different" as appropriate.

输入

Please Input Input Here

输出

Please Input Output Here

样例输入

2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

样例输出

different
same

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip Dreams孤独患者 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist