Как программно заключить в скобки выражение?

Question

У меня есть идея создать простую программу, которая поможет мне с приоритетом операторов в таких языках, как 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.

(Это не вся идея моей программы, это только первый шаг.)

Answer 1

Вам понадобится какой-то синтаксический анализатор, который понимает приоритет оператора. Обычная версия для C - это Lexx / Yacc или flex / bison, и самый простой способ сделать это - построить дерево разбора. Как только вы это сделаете, просто ходите по дереву разбора в порядке «предзаказа» и выбрасывайте парены, когда входите и выходите из узла.

Answer 2

Наиболее надежным способом будет синтаксический анализ выражения (конечно, с учетом правил приоритета ) и последующая обработка результирующего AST (абстрактного синтаксического дерева) в верхнем вниз, добавляя круглые скобки при движении

Answer 3

Как насчет конвертации в postfix и оценки. Можете ли вы попробовать, если следующий подход работает. Давайте возьмем * a.x ++

Operator    Precedence  Arguments Needed
.           3               2
++          2               1
*           1               1

Итак, теперь преобразуйте выражение в постфиксную нотацию. Это должно дать вам

a x . ++ *

Теперь оценка postfix так же проста, как помещение вещей в стек, когда вы нажимаете на оператор, выталкиваете верхние 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
Моя попытка TDDing аналогичного решения

Answer 4

Просто выберите парсер для выбранного языка, например C parser , проанализируйте выражение / исходный код и распечатайте AST обратно так, как вы хотите.

test.c:

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

Answer 5

Вы можете создать двоичное дерево выражений из операторов.

Я полагаю, что в Интернете уже есть несколько алгоритмов для создания такого дерева.

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

И затем, когда у вас есть выражение в виде двоичного дерева, вы можете затем "заключить в скобки" вверх от листьев дерева до корня.

И, конечно, вы можете скомпилировать полноценный парсер через yacc / bison.

Answer 6

Я написал программу на 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]

Answer 7

Вы можете найти "cparen" в архивах старой группы новостей net.sources.

Если вы ищете (Google) «cparen», вы получите слишком много шума, но если вы будете искать для net.sources и 'cparen.c', который сужает поиск достаточно, чтобы быть полезным.

Вот один сайт:

http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html

Это не архив оболочки, как я и ожидал. Это похоже на чистый текстовый файл ASCII. Есть несколько файлов, которые вы могли бы просто распакуйте его вручную.

Answer 8

Разбор это огромная тема. Поскольку вы просто хотите использовать его для решения конкретной проблемы, постарайтесь не погружаться во все эти конкретные алгоритмы синтаксического анализа, которые предлагают люди. Скорее, существует множество генераторов синтаксических анализаторов, таких как рога оленя или бизона, которые, при наличии соответствующей грамматики, будут анализировать текст и позволять вам выполнять программные операции над компонентами, например заключать их в круглые скобки. Некоторые из этих систем поставляются с грамматикой для C или имеют такие доступные грамматики.

antlr может генерировать парсеры на любом из упомянутых вами языков; см http://www.antlr.org/

Answer 9

В качестве простого примера:

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

Answer 10

Существует очень старая (1980-е годы) программа с открытым исходным кодом, которая делает именно это. Это называется "cparen", но я проклят, если смогу найти его в сети. Только восторженные упоминания об этом, например https://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94db http://www.language -c.info / повторное должен-я-капитализировать-константные-идентификаторы

Если вам больше повезло, чем мне найти его, напишите