Арифметическое выражение (arith.go)
Составьте программу arith.go, вычисляющую значение скобочного арифметического выражения.
Арифметическое выражение считывается из аргументов командной строки и представляет собой строку, содержащую целые числа от 0 до 2 в 31 степени, знаки четырёх арифметических операций, имена переменных, круглые скобки и пробелы. Имена переменных представляют собой последовательности латинских букв и цифр, начинающиеся с буквы. Арифметические операции — целочисленные, то есть 5/2 даёт 2, а не 2.5. Пробелы не несут никакого смысла и должны игнорироваться программой.
Примеры выражений, которые могут быть поданы на вход программе:
Грамматика для арифметических выражений записывается как
Здесь number и var обозначают множества терминальных символов, соответствующих числам и именам переменных.
После удаления левой рекурсии получается LL(1)-грамматика
Алгоритм вычисления значения выражения должен быть разбит на две части: лексический анализатор и синтаксический анализатор.
Задачей лексического анализатора является разбиение арифметического выражения на лексемы, то есть выделение в нём числовых констант, имён переменных, знаков операций и круглых скобок. Пробелы во время лексического анализа пропускаются. Каждая лексема представляется в виде экземпляра структуры Lexem:
Здесь Image — подстрока арифметического выражения, соответствующая распознанной лексеме, а Tag — целочисленный код, задающий тип лексемы:
Значения кодов лексем образуют степени двойки, чтобы можно было эффективно проверять принадлежность текущей лексемы некоторому множеству лексем. Например, если lx — переменная, в которой хранится текущая лексема, то проверить, является ли она аддитивной арифметической операцией, можно следующим образом:
Лексический анализатор должен выполняться в отдельной go-программе, получающей на вход арифметическое выражение и канал лексем и отправляющей распознанные лексемы в этот канал:
Синтаксический анализатор должен быть составлен методом рекурсивного спуска по приведённой LL(1)-грамматике.
Программа должна запрашивать у пользователя значения переменных, входящих в выражение, и выводить в стандартный поток вывода значение выражения или сообщение «error», если выражение содержит синтаксическую ошибку. Если некоторая переменная входит в выражение многократно, её значение всё равно должно запрашиваться только один раз.
@golang_interview
Составьте программу arith.go, вычисляющую значение скобочного арифметического выражения.
Арифметическое выражение считывается из аргументов командной строки и представляет собой строку, содержащую целые числа от 0 до 2 в 31 степени, знаки четырёх арифметических операций, имена переменных, круглые скобки и пробелы. Имена переменных представляют собой последовательности латинских букв и цифр, начинающиеся с буквы. Арифметические операции — целочисленные, то есть 5/2 даёт 2, а не 2.5. Пробелы не несут никакого смысла и должны игнорироваться программой.
Примеры выражений, которые могут быть поданы на вход программе:
-x * (x+10) * (128/x-5)
Length * Height * DepthГрамматика для арифметических выражений записывается как
<E> ::= <E> + <T> | <E> - <T> | <T>.
<T> ::= <T> * <F> | <T> / <F> | <F>.
<F> ::= <number> | <var> | ( <E> ) | - <F>.Здесь number и var обозначают множества терминальных символов, соответствующих числам и именам переменных.
После удаления левой рекурсии получается LL(1)-грамматика
<E> ::= <T> <E'>.
<E'> ::= + <T> <E'> | - <T> <E'> | .
<T> ::= <F> <T'>.
<T'> ::= * <F> <T'> | / <F> <T'> | .
<F> ::= <number> | <var> | ( <E> ) | - <F>.Алгоритм вычисления значения выражения должен быть разбит на две части: лексический анализатор и синтаксический анализатор.
Задачей лексического анализатора является разбиение арифметического выражения на лексемы, то есть выделение в нём числовых констант, имён переменных, знаков операций и круглых скобок. Пробелы во время лексического анализа пропускаются. Каждая лексема представляется в виде экземпляра структуры Lexem:
type Lexem struct {
Tag
Image string
}Здесь Image — подстрока арифметического выражения, соответствующая распознанной лексеме, а Tag — целочисленный код, задающий тип лексемы:
type Tag int
const (
ERROR Tag = 1 << iota // Неправильная лексема
NUMBER // Целое число
VAR // Имя переменной
PLUS // Знак +
MINUS // Знак -
MUL // Знак *
DIV // Знак /
LPAREN // Левая круглая скобка
RPAREN // Правая круглая скобка
)Значения кодов лексем образуют степени двойки, чтобы можно было эффективно проверять принадлежность текущей лексемы некоторому множеству лексем. Например, если lx — переменная, в которой хранится текущая лексема, то проверить, является ли она аддитивной арифметической операцией, можно следующим образом:
if lx.Tag & (PLUS | MINUS) != 0 {
...
}Лексический анализатор должен выполняться в отдельной go-программе, получающей на вход арифметическое выражение и канал лексем и отправляющей распознанные лексемы в этот канал:
func lexer(expr string, lexems chan Lexem) {
...
}Синтаксический анализатор должен быть составлен методом рекурсивного спуска по приведённой LL(1)-грамматике.
Программа должна запрашивать у пользователя значения переменных, входящих в выражение, и выводить в стандартный поток вывода значение выражения или сообщение «error», если выражение содержит синтаксическую ошибку. Если некоторая переменная входит в выражение многократно, её значение всё равно должно запрашиваться только один раз.
@golang_interview