1130. Infix Expression 中序遍历 数组下标可以为负

简介: //a[-1]就跟*(a-1)一样 不影响本程序结果Given a syntax tree (binary), you are supposed to output the corresponding infix e...
//a[-1]就跟*(a-1)一样   不影响本程序结果

Given a syntax tree (binary), you are supposed to output the corresponding infix expression, with parentheses reflecting the precedences of the operators.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N ( <= 20 ) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:

data left_child right_child

where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by -1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

Figure 1
Figure 2
Output Specification:

For each case, print in a line the infix expression, with parentheses reflecting the precedences of the operators. Note that there must be no extra parentheses for the final expression, as is shown by the samples. There must be no space between any symbols.

Sample Input 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Sample Output 1:
(a+b)(c(-d))
Sample Input 2:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
Sample Output 2:
(a*2.35)+(-(str%871))

#include <iostream>
#include <vector>
using namespace std;

struct node{
    string val;
    int left, right;
};
vector<node> v;
int n, root = 1;

//每一棵子树的左右两端都要加括号
string dfs(int index){
    if(index == -1) return "";
    if(v[index].right != -1){//不存在只有左子树没有右子树的情况
        v[index].val = dfs(v[index].left) + v[index].val + dfs(v[index].right);
        if (index != root) v[index].val = '(' + v[index].val + ')';
    }
    return v[index].val;
}

int main(){
    cin >> n;
    v.resize(n+1);
    vector<bool> visit(n + 1, false);//用来标记非根结点

    for (int i = 1; i <= n; i++) {
        cin >> v[i].val >> v[i].left >> v[i].right;
        if(v[i].left != -1) visit[v[i].left] = true;
        if(v[i].right != -1) visit[v[i].right] = true;
    }

    while (visit[root] == true) root++;//找到根结点
    cout << dfs(root) << endl;

    return 0;
}


目录
相关文章
|
存储 API C语言
C语言函数大全--e开头的函数
【6月更文挑战第6天】本篇介绍 C语言中 e开头的函数【C语言函数大全】
258 16
C语言函数大全--e开头的函数
|
存储 安全 算法
数字堡垒之下:网络安全漏洞、加密技术与安全意识的三维防线
在数字化时代的浪潮中,网络安全成为保护信息资产的重要屏障。本文深入探讨了网络安全的三大支柱:网络漏洞的识别与防范、加密技术的应用与挑战、以及培养安全意识的必要性。通过分析最新的统计数据和案例研究,本文揭示了网络攻击的常见模式、加密技术的发展趋势,并强调了提升个人与企业的安全意识在预防网络威胁中的核心作用。旨在为读者提供一套综合的网络安全知识框架,以应对日益复杂的网络威胁环境。
|
存储 机器学习/深度学习 人工智能
展望AI时代,把握文档图像智能分析与处理的未来
二、视觉- 语言预训练模型及迁移学习方法 三、智能文档处理技术在工业界的应用与挑战
566 2
|
存储 监控 并行计算
X86 vs ARM 架构同台竞技: 生物大数据大规模并行计算(如何将WGS全基因组计算成本降到1美元)
Sentieon DNAseq 实施的全基因组测序 (WGS) 二级分析流程与行业标准的 BWA-GATK 最佳实践流程结果相匹配,且运行速度提高了 5-20 倍。 Sentieon软件安装简单,开箱即用,并且提供了与ARM和x86指令集适配的版本。使30X WGS 数据样本在OCI 实例上的计算成本压缩到每个样本 1 美元以下,处理时间缩短到近一小时。
442 0
X86 vs ARM 架构同台竞技: 生物大数据大规模并行计算(如何将WGS全基因组计算成本降到1美元)
|
负载均衡 Java Spring
SpringCloud Gateway整合Eureka转发服务请求
`Spring Cloud Gateway`可以根据配置的`断言、谓语`进行满足条件转发,也可以自动同步`服务注册中心`的服务列表进行指定`serviceId`前缀进行转发,这里的`serviceId`是业务服务的`spring.application.name`配置参数。
|
JavaScript
ES6--》JS中Set 和 Map数据结构
对ES6中Set 和 Map 数据结构讲解
215 0
ES6--》JS中Set 和 Map数据结构
|
缓存 网络协议 网络安全
15 GitHub 使用中的记录总结
使用 ssh 连接 git 仓库 生成 ssh 密钥
192 0
15 GitHub 使用中的记录总结
|
数据采集 存储 弹性计算
二次元手游的数智进化
阿里云日志服务从内测期便伴随米哈游《原神》团队一同成长,从测试到公测,从正式上线发布到全球累计大量用户,日志服务一如既往的高性能,高稳定得到了米哈游的广泛认可与赞扬。
1032 1
二次元手游的数智进化
|
存储 缓存 前端开发
【Android 性能优化】布局渲染优化 ( 过渡绘制 | 背景设置产生的过度绘制 | Android 系统的渲染优化 | 自定义布局渲染优化 )
【Android 性能优化】布局渲染优化 ( 过渡绘制 | 背景设置产生的过度绘制 | Android 系统的渲染优化 | 自定义布局渲染优化 )
298 0
【Android 性能优化】布局渲染优化 ( 过渡绘制 | 背景设置产生的过度绘制 | Android 系统的渲染优化 | 自定义布局渲染优化 )
|
SQL 关系型数据库 MySQL
突破Java面试(50)-MySQL读写分离及主从同步延时解决方案
有没有做过MySQL读写分离 如何实现MySQL的读写分离 主从复制原理 如何解决MySQL主从同步的延时问题
4837 0