Польская запись — это форма записи арифметических, логических и алгебраических выражений, в которой операция располагается слева от операндов. Выражения в польской записи могут обходиться без скобок, однако мы оставим скобки для наглядности.
Например, выражение в польской записи выглядит как
(* 5 (+ 3 4))Пусть выражения в польской записи состоят из имён переменных (от a до z), круглых скобок и трёх знаков операций: #, $ и @ (смысл операций мы определять не будем).
Выражения могут содержать повторяющиеся подвыражения. Экономное вычисление таких выражений подразумевает, что повторяющиеся подвыражения вычисляются только один раз.
Требуется составить программу econom.go, вычисляющую количество операций, которые нужно выполнить для экономного вычисления выражения. Примеры работы программы приведены в таблице:
Набор тестов для программы экономного вычисления выражений в польской записи
Выражение Количество операций
x 0
($xy) 1
($(@ab)c) 2
(#i($jk)) 2
(#($ab)($ab)) 2
(@(#ab)($ab)) 3
(#($a($b($cd)))(@($b($cd))($a($b($cd))))) 5
(#($(#xy)($(#ab)(#ab)))(@z($(#ab)(#ab)))) 6
Решение
package main
func main() {
println(opCount("(#($(#xy)($(#ab)(#ab)))(@z($(#ab)(#ab))))"))
println(opCount("($xy)"))
println(opCount("x"))
}
func opCount(expr string) int {
expressions := map[string]bool{}
var openBraces []int
for i, c := range expr {
switch c {
case '(':
openBraces = append(openBraces, i)
case ')':
lastOpenBrace := len(openBraces) - 1
subExprStart := openBraces[lastOpenBrace]
subExpr := expr[subExprStart:i]
expressions[subExpr] = true
openBraces = openBraces[:lastOpenBrace]
}
}
return len(expressions)
}
Скобки очень сильно упрощают задачу, при этом в настоящей польской нотации скобки не нужны.
Приведем вариант кода без скобок.
const oper = node_t("oper")
const expr = node_t("expr")
type node struct {
t node_t
v string
}
func opCount(input string) int {
expressions := map[string]bool{}
var stack []node
for _, c := range input {
switch c {
case '$', '#', '@':
stack = append(stack, node{t: oper, v: fmt.Sprintf("%s", c)})
default:
stack = append(stack, node{t: expr, v: fmt.Sprintf("%s", c)})
}
for canFold(stack) {
lastIdx := len(stack) - 1
operIdx := lastIdx - 2
folded := node{t: expr, v: stack[operIdx].v + stack[operIdx+1].v + stack[operIdx+2].v}
expressions[folded.v] = true
stack[operIdx] = folded
stack = stack[:operIdx+1]
}
}
return len(expressions)
}
func canFold(stack []node) bool {
stackLen := len(stack)
return stackLen >= 3 && stack[stackLen-3].t == oper && stack[stackLen-2].t == expr && stack[stackLen-1].t == expr
}Пишите свое решение в комментариях👇
@golang_interview