Помогите с примером

Question

1.6 Экономное вычисление выражений в польской записи (econom.go, 4 балла) Пусть выражения в польской записи состоят из имён переменных (от a до z), круглых скобок и трёх знаков операций: #, $ и @ (смысл операций мы определять не будем).

Выражения могут содержать повторяющиеся подвыражения. Экономное вычисление таких выражений подразумевает, что повторяющиеся подвыражения вычисляются только один раз.

Требуется составить программу econom.go, вычисляющую количество операций, которые нужно выполнить для экономного вычисления выражения. Примеры работы программы приведены в таблице:

Набор тестов для программы экономного вычисления выражений в польской записи Что должно быть на выходе

(#($(#xy)($(#ab)(#ab)))(@z($(#ab)(#ab)))) = 6

($xy) = 1

x=0

Я пробовал по-разному, но не получается через циклы и новый массив сделать найти похожие

res1 := strings.Count(str1, "($(#ab)(#ab))")

чтобы тут написать

res1 := strings.Count(str1, "строка для поиска")

Count думал использоватт для условия, что если будет больше 1, то считать как один

Answer 1

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

Скобки очень сильно упрощают задачу, при этом в настоящей польской нотации скобки-то и не нужны. Вот так бы выглядел код, если бы выражения записывались без скобок

package main

import "fmt"

func main() {
    println(opCount("#$#xy$#ab#ab@z$#ab#ab"))
    println(opCount("$xy"))
    println(opCount("x"))
}

type node_t = string

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
}

БЛОГ НА HUSL

Помогите с примером

Ответы (1 шт):