-
Notifications
You must be signed in to change notification settings - Fork 0
/
1086.swift
78 lines (68 loc) · 1.71 KB
/
1086.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import Foundation
class Tree {
var value: Int
var left, right: Tree?
init(_ value: Int) {
self.value = value
}
}
enum Record {
indirect case push(Int)
case pop
}
var records = [Record]()
struct Range {
let left, right: Int
var isValid: Bool {
return left >= right
}
func getRange() -> (Range?, Range?) {
var pushCount = 0, popCount = 0
for i in left + 1..<right {
switch records[i] {
case .push(_): pushCount += 1
case .pop: popCount += 1
}
if popCount > pushCount {
return (Range(left: left + 1, right: i), Range(left: i + 1, right: right))
}
}
return (nil, nil)
}
func getTree() -> Tree? {
if isValid {
return nil
} else {
switch records[left] {
case .push(let value):
let tree = Tree(value)
let (left, right) = getRange()
tree.left = left?.getTree()
tree.right = right?.getTree()
return tree
default:
return nil
}
}
}
}
var flag = true
extension Tree {
func postTravel() {
left?.postTravel()
right?.postTravel()
flag ? flag = false : print(terminator: " ")
print(value, terminator: "")
}
}
let n = Int(readLine()!)!
for _ in 0 ..< n * 2 {
let s = readLine()!
if s.hasPrefix("Push") {
let value = String(s[s.index(s.startIndex, offsetBy: 5)...])
records.append(Record.push(Int(value)!))
} else {
records.append(Record.pop)
}
}
Range(left: 0, right: n * 2).getTree()?.postTravel()