Как программно заключить выражение в круглые скобки?
https://stackoverflow.com/questions/548613
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть идея создать простую программу, которая поможет мне с приоритетом операторов в таких языках, как C.Самая сложная часть — это заключение выражения в круглые скобки.Например, я хочу это:
*a.x++ = *b.x++
Преобразовано в это:
((*(((a).(x))++)) = (*(((b).(x))++)))
Что я сделал вручную в следующих шагах:
*a.x++ = *b.x++
*(a).(x)++ = *(b).(x)++
*((a).(x))++ = *((b).(x))++
*(((a).(x))++) = *(((b).(x))++)
(*(((a).(x))++)) = (*(((b).(x))++))
((*(((a).(x))++)) = (*(((b).(x))++)))
Каков наилучший способ сделать это программно?Есть ли уже решение, которое я мог бы использовать?Я бы предпочел сделать это на PHP, C, C++, Python или Ruby.
(Это не вся идея моей программы, это только первый шаг.)
Решение
Просто подберите парсер для выбранного вами языка, например C-парсер, проанализируйте выражение/исходный код и распечатайте AST так, как вы хотите.
тест.с:
void main(void){
int c = 2;
}
Терминал:
$ python
>>> import pycparser
>>> test = pycparser.parse_file('test.c')
>>> test.show()
FileAST:
FuncDef:
Decl: main, [], []
FuncDecl:
ParamList:
Typename: []
TypeDecl: None, []
IdentifierType: ['void']
TypeDecl: main, []
IdentifierType: ['void']
Compound:
Decl: c, [], []
TypeDecl: c, []
IdentifierType: ['int']
Constant: int, 2
>>> for node in test.ext:
... print node
...
<pycparser.c_ast.FuncDef object at 0x7fe1436db750>
>>>
Другие советы
Вам понадобится какой-то анализатор, который понимает приоритет операторов.Обычная версия для C — Lexx/Yacc или flex/bison, и самый простой способ сделать это — построить дерево разбора.Как только вы это сделаете, просто пройдитесь по дереву синтаксического анализа в порядке «предварительного заказа» и выдавайте круглые скобки при входе и выходе из узла.
Самым надежным способом будет разобрать выражение (принимая во внимание правила приоритета, конечно), а затем обработать полученное AST (абстрактное синтаксическое дерево) сверху вниз, добавляя круглые скобки по мере продвижения.
Как насчет преобразования в постфикс и оценки.Можете ли вы попробовать, работает ли следующий подход.Возьмем *a.x++
Operator Precedence Arguments Needed
. 3 2
++ 2 1
* 1 1
Итак, теперь преобразуем выражение в постфиксную запись.Это должно дать вам
a x . ++ *
Теперь оценка постфикса так же проста, как помещение элементов в стек: когда вы нажимаете на оператор, извлекаете n верхних (по мере необходимости оператора) элементов и передаете их в качестве аргументов, сохраняете результаты обратно в стек.В вашем случае вместо оценки вы вернете текстовое представление операции.
Stack
Read a a
Read x x
Read . (a.x)
Read ++ ((a.x)++)
Read * (*((a.x)++))
если это поможет, вы можете посмотреть:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
Серия постов Барта де Смета о DynCalc
Моя попытка TDD найти аналогичное решение
Вы можете создать дерево двоичных выражений из операторов.
Я считаю, что в Интернете уже доступно несколько алгоритмов для создания такого дерева.
Один простой способ, который я мог придумать, - это отсортировать оператор по приоритету, а затем разделить строку на 2 части сначала с помощью оператора с наименьшим приоритетом, затем продолжить рекурсивное разделение двух других частей снова и снова, а затем, в конце концов, вы выражение будет иметь форму двоичного дерева.
А затем, когда у вас есть выражение в форме двоичного дерева, вы можете «заключить в скобки» от листьев дерева до корня.
И, конечно же, вы можете скомпилировать полноценный парсер через yacc/bison.
В качестве простого примера:
Exp = Term | Exp, AddOp, Term
Term = Factor | Term, MulOp, Factor
Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp
Вы можете использовать грамматику для написания переводов:
Exp = Term -> Term
| Exp, AddOp, Term -> (, Exp, AddOp, Term, )
Term = Factor -> Factor
| Term, MulOp, Factor -> (, Term, MulOp, Factor, )
Factor = Number -> Number
| Ident -> Ident
| PreOp, Factor -> (, PreOp, Factor, )
| (, Exp, ) -> (, Exp, )
| Factor, PostOp -> (, Factor, PostOp, )
В таком случае:
a-- + b * (a+b)
Переводится на:
((a--) + (b * ((a+b))))
Парсинг — это огромная тема.Поскольку вы просто хотите использовать его для решения конкретной проблемы, постарайтесь не погружаться во все эти конкретные алгоритмы анализа, которые предлагают люди.Скорее, существует множество генераторов синтаксических анализаторов, таких как antler или bison, которые при наличии соответствующей грамматики будут анализировать текст и позволят вам выполнять программные операции над компонентами, например заключать их в круглые скобки.Некоторые из этих систем поставляются с грамматиками для C или имеют такие грамматики.
antlr может генерировать парсеры на любом из упомянутых вами языков;видеть http://www.antlr.org/
Вы можете найти «cparen» в архивах старой группы новостей net.sources.
Если вы ищете (Google) для «cparen», вы получаете слишком много шума, но если вы ищете net.sources и «cparen.c», которые сужают поиск достаточно, чтобы быть полезным.
Вот один из сайтов:
http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html
Это не архив оболочки, как я ожидал.Он выглядит как текстовый tar-файл в чистом формате ASCII.Есть достаточно файлов, что вы можете просто распаковать его вручную.
Я написал программу на Python для заключения строки выражения в круглые скобки.
def pref(op):
print "called with op", op
ret = -1
if op == '+':
print "matched +"
ret = 1
if op == '-':
print "matched -"
ret = 2
if op == '*':
print "matched *"
ret = 3
if op == '/':
print "matched /"
ret = 4
return ret
def evaluate(expr, operand_stack, operator_stack):
print "**In evaluate**"
print operator_stack
print operand_stack
expr1 = operand_stack.pop()
expr2 = operand_stack.pop()
op = operator_stack.pop()
# Parenthesize the expression
expr = "(" + expr2 + op + expr1 + ")"
print "expr1", expr1
print "expr2", expr2
print "expr", expr
# Push the result back on the stack
operand_stack.append(expr)
print operator_stack
print operand_stack
print "**Out evaluate**"
return expr
def looper(str, expr, operator_stack, operand_stack):
l = 0
cnt = len(str)
# Loop over the input string
while l < cnt:
if str[l] in ('+', '-', '*', '/'):
print "operator found: op, index", str[l], l
print operator_stack, len(operator_stack)
x = len(operator_stack) - 1
if x > 0:
print "Comparing:", operator_stack[x], str[l]
# If op on stack has higher preference than the op in question
if (pref(operator_stack[x]) > pref(str[l])):
expr = evaluate(expr, operand_stack, operator_stack)
operator_stack.append(str[l])
else:
# Add the operand to operand stack
operand_stack.append(str[l])
l += 1
print operator_stack
print operand_stack
print "Take care of last elements"
op_cnt = len(operator_stack)
while op_cnt:
expr = evaluate(expr, operand_stack, operator_stack)
op_cnt -= 1
print operator_stack
print operand_stack
if __name__ == '__main__':
str = "a+c*d-e/w*x+a-s"
cnt = len(str)
operand_stack = []
operator_stack = []
expr = ""
looper(str, expr, operator_stack, operand_stack)
print "Output=>", operand_stack[0]
Для этого существует очень старая (1980-х годов) программа с открытым исходным кодом.Оно называется "cparen", но будь я проклят, если смогу найти его в сети.Лишь восторженные упоминания о нем, напр.https://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94dbhttp://www.language-c.info/re-should-i-capitalize-const-identifiers
Если вам повезло найти его больше, чем мне, напишите
