1. <E> -> <E> + <T>{+}
2. <E> -> <T>
3. <T> -> <T>*
{*}
4. <T> ->
5.
-> (<E>)
6.
-> a{a}
Эффективность алгоритма
Классическая задачка: перевод инфиксного выражения в какое-нить еще.
Я хочу построить бинарное дерево, а там уже нисходящими, восходящими анализами перевести в постфиксное и префиксное. Анализы-то я написала, вычисление выражения тоже, осталось дерево. В нете глянула - ничего толком нету.
У меня самой идея есть...но функция нерекурсивная будет, да и криво что-то всё..стек...ифы...
В общем, я не прошу функцию мне написать. Но если вы опишите алгоритм (подробненько;)) или какой-нить псевдо-код, то буду очень благодарна.
ЗЫ. В выражении бинарые операции (+,-,/,*) и скобочки.
Я хочу построить бинарное дерево, а там уже нисходящими, восходящими анализами перевести в постфиксное и префиксное. Анализы-то я написала, вычисление выражения тоже, осталось дерево. В нете глянула - ничего толком нету.
У меня самой идея есть...но функция нерекурсивная будет, да и криво что-то всё..стек...ифы...
В общем, я не прошу функцию мне написать. Но если вы опишите алгоритм (подробненько;)) или какой-нить псевдо-код, то буду очень благодарна.
ЗЫ. В выражении бинарые операции (+,-,/,*) и скобочки.
Цитата:
Originally posted by Fialka
Классическая задачка: перевод инфиксного выражения в какое-нить еще.
Я хочу построить бинарное дерево, а там уже нисходящими, восходящими анализами перевести в постфиксное и префиксное. Анализы-то я написала, вычисление выражения тоже, осталось дерево. В нете глянула - ничего толком нету.
У меня самой идея есть...но функция нерекурсивная будет, да и криво что-то всё..стек...ифы...
В общем, я не прошу функцию мне написать. Но если вы опишите алгоритм (подробненько;)) или какой-нить псевдо-код, то буду очень благодарна.
ЗЫ. В выражении бинарые операции (+,-,/,*) и скобочки.
Классическая задачка: перевод инфиксного выражения в какое-нить еще.
Я хочу построить бинарное дерево, а там уже нисходящими, восходящими анализами перевести в постфиксное и префиксное. Анализы-то я написала, вычисление выражения тоже, осталось дерево. В нете глянула - ничего толком нету.
У меня самой идея есть...но функция нерекурсивная будет, да и криво что-то всё..стек...ифы...
В общем, я не прошу функцию мне написать. Но если вы опишите алгоритм (подробненько;)) или какой-нить псевдо-код, то буду очень благодарна.
ЗЫ. В выражении бинарые операции (+,-,/,*) и скобочки.
А почему дерево, а не классическая реализация через стек?
Цитата:
Originally posted by AlexandrVSmirno
А почему дерево, а не классическая реализация через стек?
А почему дерево, а не классическая реализация через стек?
Во-первых, потому что я в алгоритм не въехала. :{ У меня был текст с описанием и программа на Паскале...может, конечно, просто моя лень, но...
А во-вторых, у меня будущий диплом по компиляторостроению, так что по-любому придется деревья и таблицы символов строить. Вот и решила пока на простом (хм) потренироваться.
Такие переводы делаются с помощью транслирующих грамматик с помощью стека. Напр.
конструкция {x} означает, что нужно печатать x.
a - это переменная или число.
Если запрограммировать и на вход дать напр.
(a+b)*c на выходе должен быть a b + c *
Такие переводы деревьями не делаются. Просто они рисуются в книге, чтоб лучше понять процесс.
Код:
a - это переменная или число.
Если запрограммировать и на вход дать напр.
(a+b)*c на выходе должен быть a b + c *
Такие переводы деревьями не делаются. Просто они рисуются в книге, чтоб лучше понять процесс.
Цитата:
Originally posted by rostyslav
Такие переводы деревьями не делаются. Просто они рисуются в книге, чтоб лучше понять процесс.
Такие переводы деревьями не делаются. Просто они рисуются в книге, чтоб лучше понять процесс.
"Чаще всего арифметические и логические выражения описываются при помощи бинарного дерева, которое в этом случае называется деревом-формулой...
...Легко видеть, что восходящий обход узлов посещение корня после посещения поддеревьев этого бинарного дерева дает нам запись арифметического выражения в постфиксной форме.
Нисходящий обход узлов посещение корня до посещения поддеревьев такого бинарного дерева дает нам запись арифметического выражения в префиксной форме.
Наконец, смешанный обход обход левого поддерева, затем посещение корня, а только затем - обход правого поддерева дает инфиксную запись...Если задано дерево-формула, то значение арифметического выражения легко вычисляется при известных значениях переменных путём восходящего обхода дерева."
Выдержка из наших лаб.
Так еще пример есть, правда дерево строится из выражения в постфиксной записи.
К тому же я уже столько времени над этим корпею, что теперь просто обидно все заново переписывать. Нет, я определенно не смогу так. Надо дерево. :angel
Цитата:
Originally posted by Fialka
...Легко видеть, что восходящий обход узлов посещение корня после посещения поддеревьев этого бинарного дерева дает нам запись арифметического выражения в постфиксной форме.
Нисходящий обход узлов посещение корня до посещения поддеревьев такого бинарного дерева дает нам запись арифметического выражения в префиксной форме.
...Легко видеть, что восходящий обход узлов посещение корня после посещения поддеревьев этого бинарного дерева дает нам запись арифметического выражения в постфиксной форме.
Нисходящий обход узлов посещение корня до посещения поддеревьев такого бинарного дерева дает нам запись арифметического выражения в префиксной форме.
ага.. но это дерево нужно сперва построить. и сперва например задано выражение (a + b)*c, т.е. самые нижние вершины дерева. Это что-то типа строить дом начиная с крыши. Слышал когда-то, что в Венгрии разработали такой метод (построение дома сверзу вниз) и дом даже строится быстрее. Так что может ты и права.
Цитата:
Originally posted by rostyslav
ага.. но это дерево нужно сперва построить. и сперва например задано выражение (a + b)*c, т.е. самые нижние вершины дерева. Это что-то типа строить дом начиная с крыши. Слышал когда-то, что в Венгрии разработали такой метод (построение дома сверзу вниз) и дом даже строится быстрее. Так что может ты и права.
ага.. но это дерево нужно сперва построить. и сперва например задано выражение (a + b)*c, т.е. самые нижние вершины дерева. Это что-то типа строить дом начиная с крыши. Слышал когда-то, что в Венгрии разработали такой метод (построение дома сверзу вниз) и дом даже строится быстрее. Так что может ты и права.
Издеваешься,да?P( :)
(a+b)*c
Это выражение я сделаю.
(a+b+е)*c
Я тоже сделаю.
(a+b*е)*c
А вот тут надо с приоритетами париться...
Т.е. у меня пока только мысли на бумажке, и то я уже путаюсь, а если приоритеты, то там ваще лес...
Поэтому и обратилась...
Ой. У меня мысль!!!
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
Значит на повестке два вопроса. :)
У кого какие идеи как в формулу все скобки вставить?
И надо ли оно?!? Или же можно что-то попроще?
ЗЫ. Сделать эти две функции по-отдельности проще,имхо.
ЗЗЫ. Выражение находится в векторе, так что вставлять скобочки совсем недорого...
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
Значит на повестке два вопроса. :)
У кого какие идеи как в формулу все скобки вставить?
И надо ли оно?!? Или же можно что-то попроще?
ЗЫ. Сделать эти две функции по-отдельности проще,имхо.
ЗЗЫ. Выражение находится в векторе, так что вставлять скобочки совсем недорого...
Цитата:
Originally posted by Fialka
К тому же я уже столько времени над этим корпею, что теперь просто обидно все заново переписывать. Нет, я определенно не смогу так. Надо дерево. :angel
К тому же я уже столько времени над этим корпею, что теперь просто обидно все заново переписывать. Нет, я определенно не смогу так. Надо дерево. :angel
это не заметил.
нужно добавить 2х переменных к программе напр. node1st, nodelast. И к каждому узлу +2 поля напр. _next, _prev.
И изменить алгоритм построения дерева так, чтоб например при a+b*c
Код:
<oper>
/ | \
/ | \
/ | \
/ | \
<oper> <oper> +
/ | \ |
/ | \ c
/ | \
/ | \
<oper> <oper> *
| |
| |
| |
a b
/ | \
/ | \
/ | \
/ | \
<oper> <oper> +
/ | \ |
/ | \ c
/ | \
/ | \
<oper> <oper> *
| |
| |
| |
a b
node1st указывал на вершину, которая содержит a
nodelast на вершину +
поле _next вершины a указывал на вершину b итд. Думаю понятно. И тогда построение пост. или префиксной операции по уже построенному дереву сводится к тому, что или начать с node1st и шагать по _next, или начать с nodelast и шагать по _prev.
Цитата:
Originally posted by rostyslav
нужно добавить 2х переменных к программе напр. node1st, nodelast. И к каждому узлу +2 поля напр. _next, _prev....
нужно добавить 2х переменных к программе напр. node1st, nodelast. И к каждому узлу +2 поля напр. _next, _prev....
Ничего не поняла :( , но по-поводу добавления полей - это отличная идея...
буду думать...
Цитата:
Originally posted by Fialka
Издеваешься,да?P( :)
Издеваешься,да?P( :)
не а, я на полном серьезе. Ты меня наверно путаешь с Green-ом.
Цитата:
А вот тут надо с приоритетами париться...
Чтоб сказать правду, не думал, что заметишь, что приоритеты не учитываются. Но с приоритетами парится не нужно, просто пужен еще один стек операторов. Но нужно это хорошо передумать. На это буду иметь время только в след. неделю.
Цитата:
Т.е. у меня пока только мысли на бумажке, и то я уже путаюсь, а если приоритеты, то там ваще лес...Поэтому и обратилась...
я так и думал, прочитав первый пост, что есть задача и не знаешь с какой стороны подойти... :)
Цитата:
Originally posted by Fialka
Ничего не поняла :( , но по-поводу добавления полей - это отличная идея...
буду думать...
Ничего не поняла :( , но по-поводу добавления полей - это отличная идея...
буду думать...
я так помнил, что все есть, т.е. дерево построено, нужен только эффективный алгоритм выбора из этого дерева пост.или преф.записи. Но как раз дерева нету. :{
Его можно построить только с помощью конечного автомата с стековой памятью, но это лишняя работа.
Цитата:
Originally posted by rostyslav
Его можно построить только с помощью конечного автомата с стековой памятью, но это лишняя работа.
Его можно построить только с помощью конечного автомата с стековой памятью, но это лишняя работа.
А как насчет:
Цитата:
Originally posted by Fialka
Ой. У меня мысль!!!
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
Ой. У меня мысль!!!
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
???
Цитата:
Originally posted by rostyslav
Чтоб сказать правду, не думал, что заметишь, что приоритеты не учитываются. Но с приоритетами парится не нужно, просто пужен еще один стек операторов. Но нужно это хорошо передумать. На это буду иметь время только в след. неделю.
я так и думал, прочитав первый пост, что есть задача и не знаешь с какой стороны подойти... :)
Чтоб сказать правду, не думал, что заметишь, что приоритеты не учитываются. Но с приоритетами парится не нужно, просто пужен еще один стек операторов. Но нужно это хорошо передумать. На это буду иметь время только в след. неделю.
я так и думал, прочитав первый пост, что есть задача и не знаешь с какой стороны подойти... :)
Про приоритеты - это я про свой алгоритм написала, который я продумывала...
Похожу, буду ждать следующей недели. :)
Да. Не знаю. И боюсь. :)
Цитата:
Originally posted by Fialka
А как насчет:
Ой. У меня мысль!!!
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
А как насчет:
Ой. У меня мысль!!!
Если сначала преобразовать инфиксное выражение так, что бы скобочки все расставились,т.е даже где a+b+c сделать (a+b)+c, ну и т.д. Тогда по такой формуле очень просто дерево строить.
Здесь не в выражениях проблема, а в том, что дерево строится снизу в вверх. При нормальном построении есть вершина и можно двигаться по узлам вниз. А здесь сперва несколько не связанных с друг другом узлов.
Цитата:
Originally posted by rostyslav
Здесь не в выражениях проблема, а в том, что дерево строится снизу в вверх. При нормальном построении есть вершина и можно двигаться по узлам вниз. А здесь сперва несколько не связанных с друг другом узлов.
Здесь не в выражениях проблема, а в том, что дерево строится снизу в вверх. При нормальном построении есть вершина и можно двигаться по узлам вниз. А здесь сперва несколько не связанных с друг другом узлов.
Эээ...
Я вообще-то сверху вниз и иду...
Сделала одно звено. А дальше, если буква, то просто снизу еще одно добавила. Если знак, тоже просто засунуть.Когда скобочки, то создаю снизу структуру, и перескакиваю на нее...
Снизу вверх идти..это ж надо сначало как-то заковыристо сохранить в стеки, а потом еще как-то заковыристо вытащить, что бы дерево построить.
А если сверху вниз строить, то просто заковыристо строить надо. :)
Хотя...знаешь, бывает так, вот есть одно решение, и в другом направлении вообще не думается, просто ступор какой-то...у меня, возможно, именно так.
Я попробую сегодня ночью хоть примерно написать мысли на С. Может тогда что-нить придумаем...
Цитата:
Originally posted by Fialka
Эээ...
Я вообще-то сверху вниз и иду...
Сделала одно звено. А дальше, если буква, то просто снизу еще одно добавила. Если знак, тоже просто засунуть.Когда скобочки, то создаю снизу структуру, и перескакиваю на нее...
Снизу вверх идти..это ж надо сначало как-то заковыристо сохранить в стеки, а потом еще как-то заковыристо вытащить, что бы дерево построить.
А если сверху вниз строить, то просто заковыристо строить надо. :)
Хотя...знаешь, бывает так, вот есть одно решение, и в другом направлении вообще не думается, просто ступор какой-то...у меня, возможно, именно так.
Я попробую сегодня ночью хоть примерно написать мысли на С. Может тогда что-нить придумаем...
Эээ...
Я вообще-то сверху вниз и иду...
Сделала одно звено. А дальше, если буква, то просто снизу еще одно добавила. Если знак, тоже просто засунуть.Когда скобочки, то создаю снизу структуру, и перескакиваю на нее...
Снизу вверх идти..это ж надо сначало как-то заковыристо сохранить в стеки, а потом еще как-то заковыристо вытащить, что бы дерево построить.
А если сверху вниз строить, то просто заковыристо строить надо. :)
Хотя...знаешь, бывает так, вот есть одно решение, и в другом направлении вообще не думается, просто ступор какой-то...у меня, возможно, именно так.
Я попробую сегодня ночью хоть примерно написать мысли на С. Может тогда что-нить придумаем...
Ok :)
Всё. Не могу. Хррр....
Цитата:
Originally posted by rostyslav
Здесь не в выражениях проблема, а в том, что дерево строится снизу в вверх. При нормальном построении есть вершина и можно двигаться по узлам вниз. А здесь сперва несколько не связанных с друг другом узлов.
Здесь не в выражениях проблема, а в том, что дерево строится снизу в вверх. При нормальном построении есть вершина и можно двигаться по узлам вниз. А здесь сперва несколько не связанных с друг другом узлов.
А если сначала постороить конечный автомат, а потом по нему двоичное дерево. У Кнута есть на эту тему. Кажется Том2.
ЗЫ: И еще присоветую посмотреть книгу Дейкстра. "Основы компиляции".
Цитата:
Originally posted by Fialka
Всё. Не могу. Хррр....
Всё. Не могу. Хррр....
вообще никогда этой темой не интересовался но наверное в професиональных компиляторах на отдельном языке пишется синтаксис, и отдельно код его интерпретирующий. Если (не дай бог) заставят компилятор писать так и буду делать, позволит избежать уймы проблем...
Цитата:
Originally posted by AlexandrVSmirno
А если сначала постороить конечный автомат, а потом по нему двоичное дерево. У Кнута есть на эту тему. Кажется Том2.
ЗЫ: И еще присоветую посмотреть книгу Дейкстра. "Основы компиляции".
А если сначала постороить конечный автомат, а потом по нему двоичное дерево. У Кнута есть на эту тему. Кажется Том2.
ЗЫ: И еще присоветую посмотреть книгу Дейкстра. "Основы компиляции".
Ага. Посмотрела. Кое-что в Кнуте есть, кое что у Аха/Ульмана. Думаю, теперь справлюсь.
Спасибо.
Дейкстр? Хм..надо будет поискать...по-любому пригодиться, раз уже мне с этим всем еще 1,5 года страдать.
Цитата:
Originally posted by Fialka
Ага. Посмотрела. Кое-что в Кнуте есть, кое что у Аха/Ульмана. Думаю, теперь справлюсь.
Спасибо.
Дейкстр? Хм..надо будет поискать...по-любому пригодиться, раз уже мне с этим всем еще 1,5 года страдать.
Ага. Посмотрела. Кое-что в Кнуте есть, кое что у Аха/Ульмана. Думаю, теперь справлюсь.
Спасибо.
Дейкстр? Хм..надо будет поискать...по-любому пригодиться, раз уже мне с этим всем еще 1,5 года страдать.
Гм... если нарисовать синтаксис языка ариф.выражений в виде конечного автомата, то возникает мысль реализовать его парсер через паттерн StateMachine. Надо будет стопудово попробовать....заманчиво все это выглядит...я помню на такой задачке меня лет 10 назад завалили(или просто уморили)....алгоритмическая часть мышления у меня после знакомства с ООП сильно пострадала ;)..может теперь с помощью ООП получится это сделать
Цитата:
Originally posted by PitxBull
Гм... если нарисовать синтаксис языка ариф.выражений в виде конечного автомата, то возникает мысль реализовать его парсер через паттерн StateMachine. Надо будет стопудово попробовать....заманчиво все это выглядит...я помню на такой задачке меня лет 10 назад завалили(или просто уморили)....алгоритмическая часть мышления у меня после знакомства с ООП сильно пострадала ;)..может теперь с помощью ООП получится это сделать
Гм... если нарисовать синтаксис языка ариф.выражений в виде конечного автомата, то возникает мысль реализовать его парсер через паттерн StateMachine. Надо будет стопудово попробовать....заманчиво все это выглядит...я помню на такой задачке меня лет 10 назад завалили(или просто уморили)....алгоритмическая часть мышления у меня после знакомства с ООП сильно пострадала ;)..может теперь с помощью ООП получится это сделать
Классно!
В каждом посте PitxBull мы узнаем что-то новое... о нем и о кто-то себе.
Но, правда, ничего по теме топика... но это видимо из-за того, что "к сожалению ввиду низкого уровня развития твоего (т.е. моего) мышления тебе (т.е. мне) никогда не понять истинного смысла этого утвержедния."
Для PitxBull:
В этом форуме люди задают вопросы и отвечают на них, а не рассказывают о себе и своем крутом файл-менеджере. Для этого есть раздел "Отдохнем :)", милости прошу в него!
P.S. Ссорри за оффтоп.
Цитата:
Originally posted by Green
Классно!
В каждом посте PitxBull мы узнаем что-то новое... о нем и о кто-то себе.
Но, правда, ничего по теме топика... но это видимо из-за того, что "к сожалению ввиду низкого уровня развития твоего (т.е. моего) мышления тебе (т.е. мне) никогда не понять истинного смысла этого утвержедния."
Для PitxBull:
В этом форуме люди задают вопросы и отвечают на них, а не рассказывают о себе и своем крутом файл-менеджере. Для этого есть раздел "Отдохнем :)", милости прошу в него!
P.S. Ссорри за оффтоп.
Классно!
В каждом посте PitxBull мы узнаем что-то новое... о нем и о кто-то себе.
Но, правда, ничего по теме топика... но это видимо из-за того, что "к сожалению ввиду низкого уровня развития твоего (т.е. моего) мышления тебе (т.е. мне) никогда не понять истинного смысла этого утвержедния."
Для PitxBull:
В этом форуме люди задают вопросы и отвечают на них, а не рассказывают о себе и своем крутом файл-менеджере. Для этого есть раздел "Отдохнем :)", милости прошу в него!
P.S. Ссорри за оффтоп.
Green, по моему ты болен.
Вроде как это известный алгоритм разбора выражения. Результаты разбора пишутся в стек. Но этот стек можно рассматривать и как дерево. А можно и сразу дерево вида
Ну а вот, собственно и сам алгоритм. Рассмотрим выражения вида (a + b + c * d) / e. Разобъем на три группы приоритета:
1. Операции +, -
2. Операции *, /
3. Переменные (a, b, c, итп) и скобки.
То есть, с расставленными приоритетами мы сначала считаем значения переменных, затем мы считаем то, что внутри скобок, затем мы считаем умножения-деления (слева-направо, т.е a*b/c = (a*b) / c), затем считаем вычитания-сложения.
Для каждого приоритета пишем три функции:
1. ParseAddition() - для +, -
2. ParseMultiplication() - для *, /
3. ParseOther() - для всего остального.
Ну а сами функции делаем так:
Вот такой вот код, например, из выражения a+b+c он построит дерево:
А из выражения (a + b + c * d) / e
Он построит дерево:
Код:
struct STree
{
SLeaf m_leaf;
STree* m_pLeft;
STree* m_pRight;
}
{
SLeaf m_leaf;
STree* m_pLeft;
STree* m_pRight;
}
Ну а вот, собственно и сам алгоритм. Рассмотрим выражения вида (a + b + c * d) / e. Разобъем на три группы приоритета:
1. Операции +, -
2. Операции *, /
3. Переменные (a, b, c, итп) и скобки.
То есть, с расставленными приоритетами мы сначала считаем значения переменных, затем мы считаем то, что внутри скобок, затем мы считаем умножения-деления (слева-направо, т.е a*b/c = (a*b) / c), затем считаем вычитания-сложения.
Для каждого приоритета пишем три функции:
1. ParseAddition() - для +, -
2. ParseMultiplication() - для *, /
3. ParseOther() - для всего остального.
Ну а сами функции делаем так:
Код:
void ParseAddition()
{
ParseMultiplication();
while (currentSymbol == '+' ||
currentSymbol == '-')
{
STree* pNewRoot = new STree();
pNewRoot->m_leaf.opeartion = currentSymbol;
pNewRoot->m_left = pRoot;
ParseMultiplication();
pNewRoot->m_right = pRoot;
pRoot = pNewRoot;
}
}
void ParseMultiplication()
{
ParseOther();
while (currentSymbol == '*'||
currentSymbol == '/')
{
STree* pNewRoot = new STree();
pNewRoot->m_leaf.opeartion = currentSymbol;
pNewRoot->m_left = pRoot;
ParseOther();
pNewRoot->m_right = pRoot;
pRoot = pNewRoot;
}
}
void ParseOther()
{
if (currentSymbol == '(')
{
ParseAddition();
if (currentSymbol != ')')
{
//Синтаксическая ошибка
}
}
else if (currentSymbol == 'a' ||
currentSymbol == 'b' || ...)
{
STree* pRoot = new STree();
pRoot->m_leaf.opeartion = currentSymbol;
pRoot->m_left = NULL;
pRoot->m_right = NULL;
}
else
{
//Синтаксическая ошибка
}
}
{
ParseMultiplication();
while (currentSymbol == '+' ||
currentSymbol == '-')
{
STree* pNewRoot = new STree();
pNewRoot->m_leaf.opeartion = currentSymbol;
pNewRoot->m_left = pRoot;
ParseMultiplication();
pNewRoot->m_right = pRoot;
pRoot = pNewRoot;
}
}
void ParseMultiplication()
{
ParseOther();
while (currentSymbol == '*'||
currentSymbol == '/')
{
STree* pNewRoot = new STree();
pNewRoot->m_leaf.opeartion = currentSymbol;
pNewRoot->m_left = pRoot;
ParseOther();
pNewRoot->m_right = pRoot;
pRoot = pNewRoot;
}
}
void ParseOther()
{
if (currentSymbol == '(')
{
ParseAddition();
if (currentSymbol != ')')
{
//Синтаксическая ошибка
}
}
else if (currentSymbol == 'a' ||
currentSymbol == 'b' || ...)
{
STree* pRoot = new STree();
pRoot->m_leaf.opeartion = currentSymbol;
pRoot->m_left = NULL;
pRoot->m_right = NULL;
}
else
{
//Синтаксическая ошибка
}
}
Вот такой вот код, например, из выражения a+b+c он построит дерево:
Код:
+
/ \
+ c
/ \
a b
/ \
+ c
/ \
a b
А из выражения (a + b + c * d) / e
Он построит дерево:
Код:
'/'
/ \
+ e
/ \
+ *
/ \ / \
a bc d
/ \
+ e
/ \
+ *
/ \ / \
a bc d
Цитата:
Originally posted by Fialka
Дейкстр? Хм..надо будет поискать...по-любому пригодиться, раз уже мне с этим всем еще 1,5 года страдать.
Дейкстр? Хм..надо будет поискать...по-любому пригодиться, раз уже мне с этим всем еще 1,5 года страдать.
Фамилия у него смешная [color=red]Дейкстра[/color].
Цитата:
Originally posted by PitxBull
Гм... если нарисовать синтаксис языка ариф.выражений в виде конечного автомата, то возникает мысль реализовать его парсер через паттерн StateMachine.
Гм... если нарисовать синтаксис языка ариф.выражений в виде конечного автомата, то возникает мысль реализовать его парсер через паттерн StateMachine.
Если честно, то мне что парсер, что паттерн, одна фигня - загадочные словечки. :)
Грин - злюка. ;)
S_T, ого, ты это сам придумал? Я там запуталась. Попробовала взять (a+b+c*d)/e и сделать все тупо по-шагам на бумажке. Но там одна ф-ция вызывает другую, другая еще одну, и так по кругу, так что после 4 вызовов я вылетела, если честно. :(
ЗЫ. А что за квадратик такой загадочный напротив этой темы?
Цитата:
Originally posted by S_T
Код:
else if (currentSymbol == 'a' ||
currentSymbol == 'b' || ...)
currentSymbol == 'b' || ...)
Кстати, кстати, как раз собиралась спросить...
Вот если мне надо много-много всего перечислить...
В паскале было что-то вроде:
Код:
If Str IN ['a'..'z' or 'A'..'Z']
then { код }
then { код }
А в С/С++ такое есть? Мне, когда было нужно проверить на принадлежность алфавиту, я коды символов сравнивала, тогда, когда смотришь в каком промежутке символ - это короче, чем все символы перечислять. Есть что-то получше?
Цитата:
Originally posted by Fialka
Кстати, кстати, как раз собиралась спросить...
Вот если мне надо много-много всего перечислить...
В паскале было что-то вроде:
А в С/С++ такое есть? Мне, когда было нужно проверить на принадлежность алфавиту, я коды символов сравнивала, тогда, когда смотришь в каком промежутке символ - это короче, чем все символы перечислять. Есть что-то получше?
Кстати, кстати, как раз собиралась спросить...
Вот если мне надо много-много всего перечислить...
В паскале было что-то вроде:
Код:
If Str IN ['a'..'z' or 'A'..'Z']
then { код }
then { код }
А в С/С++ такое есть? Мне, когда было нужно проверить на принадлежность алфавиту, я коды символов сравнивала, тогда, когда смотришь в каком промежутке символ - это короче, чем все символы перечислять. Есть что-то получше?
Есть специальные функции, например isalpha
Цитата:
Originally posted by Fialka
Если честно, то мне что парсер, что паттерн, одна фигня - загадочные словечки. :)
Грин - злюка. ;)
S_T, ого, ты это сам придумал? Я там запуталась. Попробовала взять (a+b+c*d)/e и сделать все тупо по-шагам на бумажке. Но там одна ф-ция вызывает другую, другая еще одну, и так по кругу, так что после 4 вызовов я вылетела, если честно. :(
ЗЫ. А что за квадратик такой загадочный напротив этой темы?
Если честно, то мне что парсер, что паттерн, одна фигня - загадочные словечки. :)
Грин - злюка. ;)
S_T, ого, ты это сам придумал? Я там запуталась. Попробовала взять (a+b+c*d)/e и сделать все тупо по-шагам на бумажке. Но там одна ф-ция вызывает другую, другая еще одну, и так по кругу, так что после 4 вызовов я вылетела, если честно. :(
ЗЫ. А что за квадратик такой загадочный напротив этой темы?
Нет этот алгоритм я сам не придумывал. Вроде это один из стандартных алгоритмов разбора арифметического выражения. Кстати, очень легко распространяется на множество других операций, а так же на наличие функций (например, sin(выражение) или f(выражение1, выражение2, выражение3, ...) итп).
А лучше почитать какие нибудь книги - можно найти подробное описание подобных алгоритмов. Искать надо по ключевой фразе - "Форма Бекуса-Наура".
Насчет квадратика - я не понял...
Цитата:
Originally posted by Fialka
Кстати, кстати, как раз собиралась спросить...
Вот если мне надо много-много всего перечислить...
В паскале было что-то вроде:
А в С/С++ такое есть? Мне, когда было нужно проверить на принадлежность алфавиту, я коды символов сравнивала, тогда, когда смотришь в каком промежутке символ - это короче, чем все символы перечислять. Есть что-то получше?
Кстати, кстати, как раз собиралась спросить...
Вот если мне надо много-много всего перечислить...
В паскале было что-то вроде:
Код:
If Str IN ['a'..'z' or 'A'..'Z']
then { код }
then { код }
А в С/С++ такое есть? Мне, когда было нужно проверить на принадлежность алфавиту, я коды символов сравнивала, тогда, когда смотришь в каком промежутке символ - это короче, чем все символы перечислять. Есть что-то получше?
Конечно есть. Нужно написать некий класс, на вход которого подается символьная строка, а на выход он выдает последовательно так называемые Лексемы (или токены или tokens). Так вот, лексема должна быть следующего рода:
Код:
enum ETokenType
{
ePlus, // +
eMinus, // -
eOpenParenthesis // (
eCloseParenthesis, // )
eIdentifier, // abcde или a156 или _abc1
eNumber, // 123.456E+001
итп
}
struct SToken
{
ETokenType m_eType;
string m_strTokenValue;
}
{
ePlus, // +
eMinus, // -
eOpenParenthesis // (
eCloseParenthesis, // )
eIdentifier, // abcde или a156 или _abc1
eNumber, // 123.456E+001
итп
}
struct SToken
{
ETokenType m_eType;
string m_strTokenValue;
}
Так вот, нужно написать соответсвтующую функцию, для разбора строки:
Код:
...
LPTSTR m_pszScan = (LPTSTR)"(a+b+c*d)/e";
...
SToken getNextToken()
{
SToken token;
if (*m_pszScan == _T('+'))
{
token.m_eType = ePlus;
m_pszScan++;
}
else if (*m_pszScan == _T('-'))
{
token.m_eType = eMinus;
m_pszScan++;
}
...
else if (_istalpha(*m_pszScan) ||
*m_pszScan == _T('_')
{
token.m_eType = eIdentifier;
do
{
token.m_strTokenValue += *m_pszScan++;
}
while (_istalpha(*m_pszScan) ||
*m_pszScan == _T('_') ||
_istdigit(*m_pszScan));
}
else if (_istdigit(*m_pszScan))
{
token.m_eType = eNumber;
...
}
}
LPTSTR m_pszScan = (LPTSTR)"(a+b+c*d)/e";
...
SToken getNextToken()
{
SToken token;
if (*m_pszScan == _T('+'))
{
token.m_eType = ePlus;
m_pszScan++;
}
else if (*m_pszScan == _T('-'))
{
token.m_eType = eMinus;
m_pszScan++;
}
...
else if (_istalpha(*m_pszScan) ||
*m_pszScan == _T('_')
{
token.m_eType = eIdentifier;
do
{
token.m_strTokenValue += *m_pszScan++;
}
while (_istalpha(*m_pszScan) ||
*m_pszScan == _T('_') ||
_istdigit(*m_pszScan));
}
else if (_istdigit(*m_pszScan))
{
token.m_eType = eNumber;
...
}
}
Тогда в соответсвующем коде разбора (функции parseXXX) нужно будет проверять только m_eType у возвращаемых лексем. И, кстати, узел дерева SLeaf может содержать в себе структуру SToken (а может ею и являться).
И все-таки, найдите книгу, почитайте и вникните. А раз это еще и относится к вашему диплому - то не бойтесь спрашивать руководителя :-)
Цитата:
Originally posted by S_T
И все-таки, найдите книгу, почитайте и вникните.
И все-таки, найдите книгу, почитайте и вникните.
IMHO далеко лучшая книга по этим вопросам (лекс./синт. анализ, разработка конечных автоматов и разных грамматик) Льюис идр. Теоретические основы проектирования компиляторов.
У Дейкстре только хорошо описана генерация команд, книга Ахо итд черезчур теоретическая (море теорем с доказательствами) - конечно, только если мне память не изменяет :).
Цитата:
Originally posted by S_T
А раз это еще и относится к вашему диплому - то не бойтесь спрашивать руководителя :-)
А раз это еще и относится к вашему диплому - то не бойтесь спрашивать руководителя :-)
На счет препода можно подумать. Если порядочный, то не стоит его терроризировать...
Цитата:
Originally posted by Fialka
Грин - злюка. ;)
Грин - злюка. ;)
2Green Sorry. Кто-то мою шутку принял в серьез :{