Добро пожаловать на Введение в структуры данных в Go! Как я и обещал, мы рассмотрим особое применение стеков. В частности, мы изучим, как преобразовывать инфиксные выражения в их постфиксные эквиваленты. Постфиксная нотация может показаться интуитивно понятной, но после этого поста она станет намного понятнее.
Краткое руководство
“Джейкоб, прошла целая неделя с твоего последнего сообщения. Я не помню, что это такое”. Правильно, давайте начнем с объяснения того, что это такое.
На уроках математики мы узнали, что выражения – это комбинация терминов и операторов, которые обычно записываются в таком формате.
a + b
Это так называемая инфиксная нотация. Это потому, что оператор находится между операндами.
Есть еще две нотации, которые мы используем для оценки выражений. Это префиксная и постфиксная нотации. Вот сравнение трех выражений.
Infix: <operand><operator><operand>
Prefix: <operator><operand><operand>
Postfix: <operand><operand><operator>
Приведенное выше выражение a + b можно записать и так:
Infix: a+b
Prefix: +ab
Postfix: ab+
Мы используем инфиксные обозначения, потому что они просты для нашего понимания. Но то, что обычно легко для нас, людей, сложно для компьютеров. Представьте, что вы пишете программу для оценки выражения. Простые выражения, такие как a + b, достаточно просты. Однако представьте, что выражения становятся сложнее.
{(a*b) + (c*d)} - e
Когда в выражении много скобок и операторов, вы можете видеть, как быстро возрастает сложность. Нам нужно не только обрабатывать операции, но и следить за их порядком. Поскольку есть вложенные круглые скобки, нам придется прыгать туда-сюда, чтобы сначала оценить выражения внутри скобок. Следить за тем, где мы находимся, было бы просто кошмаром.
Теперь посмотрите на это.
ab*cd*+e-
Постфиксная нотация намного проще, потому что нам нужно только просмотреть выражение слева направо, чтобы получить результат.
Как оценить постфиксное выражение?
Давайте рассмотрим это выражение:
ab*cd*+e-
a = 2
b = 5
c = 3
d = 1
e = 4
Сначала мы сканируем слева направо. Мы остановимся, когда увидим оператор.
2 5 * 3 1 * + 4 -
^
Как только мы увидим оператора, мы вернемся на два шага назад. Каждый раз, возвращаясь назад, мы следим за числами. Затем мы оцениваем выражение. В данном случае мы остановились на операторе умножения * и вернулись на два шага назад. Мы следим за числами 2 и 5. Для оценки достаточно выполнить 2 * 5, что дает 10. Порядок применения операций очень важен. Например, если наш оператор - вместо *, то 2 - 5 должно дать -3, но выполнение 5 - 2 вместо этого даст 3.
2 5 * 3 1 * + 4 -
^
Numbers: 5, 2
Evaluation: 2 * 5 = 10
Result:
10 3 1 * + 4 -
Отлично! Теперь нам остается только повторять описанные выше действия до тех пор, пока мы не закончим.
10 3 1 * + 4 -
^
Numbers: 1, 3
Evaluation: 3 * 1 = 3
Result:
10 3 + 4 -
10 3 + 4 -
^
Numbers: 3, 10
Evaluation: 3 + 10 = 13
Result:
13 4 -
13 4 -
^
Numbers: 4, 13
Evaluation: 13 - 4 = 9
Result:
9
В итоге мы получаем 9. Чтобы перепроверить, давайте вычислим инфиксное выражение.
Evaluate {(a*b) + (c*d)} - e, given these conditions:
a = 2, b = 5, c = 3, d = 1, e = 4
{(2 * 5) + (3 * 1)} - 4
= {10 + 3} - 4
= 13 - 4
= 9
Вуаля! Мы успешно вычислили постфиксное выражение.
Заметили, что Numbers, за которыми мы следили, действуют как стек? Когда мы видим оператор, мы возвращаемся назад два раза и заталкиваем эти числа в стек Numbers. Затем мы вытаскиваем эти числа и применяем операцию.
Преобразование ручным способом
Мы можем использовать стеки для преобразования инфиксных обозначений в постфиксные эквиваленты. Прежде чем мы обсудим, как написать это в Go, важно понять логику процесса.
Допустим, нам нужно преобразовать это выражение:
a+b*c
Что мы должны сделать, так это отслеживать операторы, подобно тому, как мы отслеживали операнды в предыдущем примере.
Сначала мы сканируем слева направо. Когда мы видим операнд, мы записываем его сбоку. Когда мы видим оператор, мы добавляем его в наш список операторов.
a + b * c
^
Operators:
Result: a
a + b * c
^
Operators: +
Result: a
a + b * c
^
Operators: +
Result: ab
a + b * c
^
Operators: +, *
Result: ab
Вот важная часть.
-
Когда добавляется оператор, необходимо проверить, имеет ли оператор, на который мы указываем, больший приоритет, чем оператор в верхней части нашего списка, используя порядок операций. Здесь оператор, на который мы указываем,
*, имеет приоритет над оператором, находящимся в начале списка,-. Умножение имеет приоритет над вычитанием. -
Если он имеет приоритет, мы просто добавляем указанный оператор в наш список операторов.
-
Если же он не имеет приоритета, мы разворачиваем список и добавляем оператор из нашего списка к строке результата. Так продолжается до тех пор, пока оператор, на который мы указываем, не получит приоритет над оператором, находящимся в верхней части нашего списка. После этого мы добавляем оператор в список.
Давайте продолжим.
a + b * c
^
Operators: +, *
Result: abc
Дойдя до конца, мы раскрываем список операторов и добавляем их элементы в строку результата, как показано ниже:
Result: abc*+
Давайте рассмотрим еще один пример.
a * b + c
^
Operators:
Result: a
---
a * b + c
^
Operators: *
Results: a
---
a * b + c
^
Operators: *
Results: ab
---
a * b + c
^
Operators: * // check for precedence before you add +!
Results: ab
Здесь мы имеем дело со вторым сценарием. Поскольку + не имеет приоритета над *, нам нужно листать список операторов до тех пор, пока + не получит приоритет. В данном случае, нам нужно листать его до тех пор, пока в списке ничего не останется.
a * b + c
^
Operators: + // + is pushed in after * is popped out
Results: ab* // * is popped and appended into the result string
Остальное просто.
a * b + c
^
Operators: +
Results: ab*c
---
Results: ab*c+
Давайте рассмотрим последний пример. На этот раз мы преобразуем выражение со скобками.
{(a*b) + (c*d)} - e
Не волнуйтесь, нам нужно добавить только одно правило.
-
Если это открывающая скобка, мы добавляем ее в список операторов.
-
Если это закрывающая скобка, мы листаем наш список до тех пор, пока не появится соответствующая скобка.
-
Нам не нужно добавлять круглые скобки к нашей строке результата. Постфиксная нотация не требует этого.
Давайте пройдемся по шагам!
{ ( a * b ) * c - d } - e
^
Operators: {, (
Result: a
---
{ ( a * b ) * c - d } - e
^
Operators: {, (, *
Result: a
---
{ ( a * b ) * c - d } - e
^
Operators: {, (, *
Result: ab
---
{ ( a * b ) * c - d } - e
^
Operators: { // pop until the corresponding parenthesis is popped
Result: ab* // * is appended
---
{ ( a * b ) * c - d } - e
^
Opeartors: {, *
Result: ab*
---
{ ( a * b ) * c - d } - e
^
Operators: {, *
Result: ab*c
---
{ ( a * b ) * c - d } - e
^
Operators: {, - // - doesn't take precedence over *
Result: ab*c* // * is popped and appended
---
{ ( a * b ) * c - d } - e
^
Operators: {, -
Result: ab*c*d
---
{ ( a * b ) * c - d } - e
^
Operators:
Result: ab*c*d-
---
{ ( a * b ) * c - d } - e
^
Operators: -
Result: ab*c*d-
---
{ ( a * b ) * c - d } - e
^
Operators: -
Result: ab*c*d-e
---
Result: ab*c*d-e-
Это выглядит сложным только потому, что мы делали это медленно, шаг за шагом. Сама логика довольно проста.
Опять же, список операторов действует как стек, потому что мы постоянно выталкиваем и выталкиваем из него.
Запишите это в go
Отлично! Теперь, когда мы поняли, как работает высокоуровневая логика, мы можем начать реализовывать ее в Go.
type Stack struct {
items []float64
}
func (s *Stack) Push(data float64) {
s.items = append(s.items, data)
}
func (s *Stack) Pop() {
if s.IsEmpty() {
return
}
s.items = s.items[:len(s.items)-1]
}
func (s *Stack) Top() (float64, error) {
if s.IsEmpty() {
return 0.0, fmt.Errorf("stack is empty")
}
return s.items[len(s.items)-1], nil
}
func (s *Stack) IsEmpty() bool {
if len(s.items) == 0 {
return true
}
return false
}
func (s *Stack) Print() {
for _, item := range s.items {
fmt.Print(item, " ")
}
}
Мы будем использовать реализацию стека из предыдущего сообщения. Этот стек может хранить типы float64.
Давайте сначала рассмотрим, как оценить постфиксное выражение.
Оценка постфиксных выражений
func evaluatePostfix(exp string) (float64, error) {
operands := new(Stack)
chars := strings.Split(exp, " ")
for _, char := range chars {
if !isOperator(char) {
op, err := strconv.ParseFloat(char, 64)
if err != nil {
return 0.0, err
}
operands.Push(op)
} else {
operand2, err := operands.Top()
if err != nil {
return 0.0, err
}
operands.Pop()
operand1, err := operands.Top()
if err != nil {
return 0.0, err
}
operands.Pop()
calculated, err := calculate(char, operand1, operand2)
if err != nil {
return 0.0, err
}
operands.Push(calculated)
}
}
result, err := operands.Top()
if err != nil {
return 0.0, err
}
return result, nil
}
Сначала разделим выражение на отдельные символы пробелом. Выражение должно представлять собой комбинацию операндов и операторов, разделенных пробелом. Теперь мы можем выполнить итерацию по полученному фрагменту символов.
Для каждого символа мы хотим проверить, является ли он операндом или оператором, используя вспомогательную функцию isOperator. Если символ является операндом, мы помещаем его в стек.
Если символ является оператором, мы вытаскиваем два самых верхних элемента в стеке, сохраняя их как operand2 и operand1. Затем мы оцениваем выражение с помощью вспомогательной функции calculate. Как только вычисление будет выполнено, мы помещаем его в стек.
После итерации по выражению мы получаем самый верхний элемент из стека, который и является нашим конечным результатом.
Ниже приведены определения вспомогательных функций.
func isOperator(char string) bool {
switch char {
case "+":
return true
case "-":
return true
case "*":
return true
case "/":
return true
default:
return false
}
}
func calculate(operator string, operand1, operand2 float64) (float64, error) {
result := 0.0
switch operator {
case "+":
result = operand1 + operand2
case "-":
result = operand1 - operand2
case "*":
result = operand1 * operand2
case "/":
result = operand1 / operand2
default:
return 0.0, fmt.Errorf("invalid operator")
}
return result, nil
}
Теперь мы можем посмотреть, как написать функцию преобразования инфикса в постфикс.
Преобразование инфикса в постфикс
Мы изменим наш стек так, чтобы он хранил типы string вместо типов float64.
func infixToPostfix(exp string) (string, error) {
operators := new(StringStack)
chars := strings.Fields(exp)
result := ""
for _, char := range chars {
if isOpeningParenthesis(char) {
operators.Push(char)
} else if isClosingParenthesis(char) {
for !operators.IsEmpty() && !isMatchingParenthesis(ignoreError(operators.Top()), char) {
top, err := operators.Top()
if err != nil {
return "", err
}
result += top
operators.Pop()
}
operators.Pop()
} else if !isOperator(char) {
result += char
} else if isOperator(char) {
for !operators.IsEmpty() && hasHigherPrecedence(ignoreError(operators.Top()), char) && !isOpeningParenthesis(ignoreError(operators.Top())) {
top, err := operators.Top()
if err != nil {
return "", err
}
result += top
operators.Pop()
}
operators.Push(char)
}
}
for !operators.IsEmpty() {
top, err := operators.Top()
if err != nil {
return "", err
}
result += top
operators.Pop()
}
return result, nil
}
Начало аналогично. Мы создаем фрагмент строки, в котором хранятся все разделенные символы. Новым здесь является то, что нам нужно разобраться с четырьмя случаями.
-
Когда символ является открывающей скобкой, мы помещаем его в стек.
-
Если символ является закрывающей скобкой, мы перетаскиваем все операторы, пока не будет найдена соответствующая открывающая скобка.
-
Когда символ является операндом, мы добавляем его к строке результата.
-
Если символ является оператором, мы проверяем старшинство. Если самый верхний оператор в стеке имеет более высокий приоритет, чем символ, мы открываем его до тех пор, пока не найдем открывающую скобку. Затем мы заталкиваем символ в стек.
В конце мы сбрасываем все, что осталось в стеке, в результирующую строку.
Ниже приведены определения вспомогательных функций.
func isOpeningParenthesis(char string) bool {
switch char {
case "(":
return true
case "{":
return true
case "[":
return true
default:
return false
}
}
func isClosingParenthesis(char string) bool {
switch char {
case ")":
return true
case "}":
return true
case "]":
return true
default:
return false
}
}
func isMatchingParenthesis(opening, closing string) bool {
switch opening {
case "(":
if closing == ")" {
return true
}
case "{":
if closing == "}" {
return true
}
case "[":
if closing == "]" {
return true
}
default:
return false
}
return false
}
func hasHigherPrecedence(target, source string) bool {
if (target == "*" || target == "/") && (source == "+" || source == "-") {
return true
} else {
return false
}
}
func ignoreError(val string, err error) string {
return val
}
Обратите внимание, что игнорирование ошибок не является хорошей практикой. Я использовал ее, чтобы справиться с раздражающими возвратами ошибок, поскольку не мог передать operators.Top() в hasHigherPrecedence или isMatchingParenthesis из-за того, что он возвращает два значения, одно из которых – ошибка. Если вы должны игнорировать подобные ошибки, вы можете определить метод struct типа stack.TopNoError(), который будет возвращать самое верхнее значение без каких-либо переменных ошибок.
Заключение
Спасибо, что прочитали! Это был длинный пост, но я горжусь тем, что вы выдержали меня. Обычно вы не сталкиваетесь с ситуациями, когда вам нужно явно преобразовать инфиксное выражение в постфиксное, потому что компилятор сделает это за вас. Тем не менее, это отличный способ узнать, как работают стеки, и я думаю, что это действительно интересная тема, которую нужно знать. Я вернусь на следующей неделе с статьей об очередях. До встречи!
Вы также можете прочитать эту статью на Medium и на моем личном сайте.