Форум программистов, компьютерный форум CyberForum.ru

Построить распознаватель языка с помощью стека - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
10.09.2012, 17:41     Построить распознаватель языка с помощью стека #1
Приветствую, преподаватель задал задачку, сказал решение маленькое, порядка строк 8-10. Сам не очень программирую, есть предложения с чего начать?


Задание:
Язык префиксных арифметических выражений определяется следующим набором БНФ:
1. <пер>::=A|B|...|Z // ("переменная")
2. <оп1>::=корень // ("унарная операция")
3. <оп2>::=+|-|*|/ // ("бинарная операция")
4. <выр>::=<пер>|<оп1><выр>|<оп2><выр><выр> // ("выражение")

Построить распознаватель этого языка с помощью стека.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.09.2012, 17:41     Построить распознаватель языка с помощью стека
Посмотрите здесь:

C++ Написать программу,которая вычисляет значение арифметического выражения записанного в постфиксной форме,с помощью стека
построить детерминированный конечный распознаватель C++
C++ Реализация стека с помощью массива
детерминированный конечный распознаватель C++
C++ Выделение в исходном коде программы ключевых слов языка и операторов языка по словарю
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kidasov
76 / 76 / 12
Регистрация: 02.12.2011
Сообщений: 966
Записей в блоге: 3
11.09.2012, 00:44     Построить распознаватель языка с помощью стека #2
Прочитайте про польскую запись http://ru.wikipedia.org/wiki/%D0%9E%...B8%D1%81%D1%8C
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//Реализация польской записи на стеке(код рабочий хотя и много лишнего, давненько я его писал)
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
 
 
template <class Item>
class Stack {
private:
    int N;
    int *a;
public:
    Stack();
    ~Stack();
    void push(int val);
    void pushStr(char *str);
    Item pop();
    void output() const;
};
 
 
template<class Item> Stack<Item> :: Stack() {
    a = new int[30];
    N = 0;
}
 
template<class Item> Stack<Item> :: ~Stack() {
    delete[] a;
    a = NULL;
}
 
template<class Item> void Stack<Item> :: output() const {
    for (int i = 0; i < N; i++) {
        std :: cout << a[i] << " ";
    }
    std :: cout << std :: endl;
}
 
template<class Item> void Stack<Item> :: push(int val) {
    a[N++] = val;
}
 
 
template<class Item> Item Stack<Item> :: pop() {
    return a[--N];
}
 
template<class Item> void Stack<Item> :: pushStr(char *str) {
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] != '-' && str[i] != '+' && str[i] != '*' && str[i] != '/' && (str[i] >= 0 || str[i] <= 9)) {
            push(str[i] - '0'); 
        }
        else {
            switch(str[i]) {
                case '+' : push(pop() + pop()); break;
                case '-' : push(pop() - pop()); break;
                case '*' : push(pop() * pop()); break;
                case '/' : push(pop() / pop()); break;
                default: std :: cout << "Error" << std :: endl;
            }
        }
    }
}
 
 
int main() {
    Stack<int> ob;
    char str[256];
    std :: cout << "Enter expression: " << std :: endl;
    gets(str);
    ob.pushStr(str);
    ob.output();
    return 0;
}
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
16.09.2012, 09:25  [ТС]     Построить распознаватель языка с помощью стека #3
Вот листинг программы, которая проверяет являетсья ли введенное выражение выражением в префиксной форме и соответственно выдает сообщение о том являеться или нет.
Вот например пишем туда ++ABC или +$AB знак доллара, это корень как будто...выраэение считывается с конца строки и если там символ, он помещается в стек, если дальше ещё символ тоже в стек, если встречается $ просто ничего не делаем переходим к следующему символу. Если встречается +-* или / то вытаскиваются два символа из стека и вместо них один неважно какой, ну или просто вытаскивается один, вот если в конце когда все выражение пройдено с конца до начала, в стеке остаётся один символ то выражение префиксное, здесь стек сделан на основе структур. Может кто делал или есть листинг на основе классов или ещё как нибудь реализованный по другому стек?

делал в билдере 6:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#pragma hdrstop
#include<fstream.h>
#include<stdlib.h>
#include<string.h>
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<iomanip.h>
 
struct prf
{char sym[2];
prf *p;
};
 
prf *first(char *sym)
{prf *temp=new prf;
strcpy(temp->sym,sym);
temp->p=NULL;
return temp;
}
 
void vstek(prf **stek, char *sym)
{prf *temp=new prf;
strcpy(temp->sym,sym);
temp->p=*stek;
*stek=temp;
}
 
char del(prf **stek)
{//char som[1];
//strcpy(som,(*stek)->sym);
prf *temp=*stek;
*stek=(*stek)->p;
delete temp;
 
}
 
void vivod(prf **stek)
{prf *temp=*stek;
while(temp)
{cout<<temp->sym<<"   ";
//cout<<endl;
temp=temp->p;}
}
 
int isprf(prf **stek)
{prf *temp=*stek;
if (temp->p==NULL)
return 1;
else
return 0;
}
 
#pragma argsused
int main(int argc, char* argv[])
{char sim[2];
char str[20]; int i=0;
cout<<"Vveite stroku: "<<endl;
cin>>str;
while(str[i]!=NULL)
{i++;}
if (isalpha(str[0])&&(str[1]=NULL))
cout<<"-------FORMA PREFIXNAJA------"<<endl;
if (isalpha(str[i-1]))
{sim[0]=str[i-1];
prf *elem=first(sim);
for(int j=i-2; j>=0; j--)
{if (isalpha(str[j]))
{sim[0]=str[j];
vstek(&elem,sim);}
else
if ((str[j]=='+')||(str[j]=='-')||(str[j]=='/')||(str[j]=='*'))
del(&elem);}
vivod(&elem);
if (isprf(&elem)==1)
cout<<endl<<"-------FORMA PREFIXNAJA------"<<endl;
else
cout<<"-------FORMA NE PREFIXNAJA------"<<endl;}
else
cout<<"-------FORMA NE PREFIXNAJA------"<<endl;
getch();
        return 0;
}
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
16.09.2012, 10:43     Построить распознаватель языка с помощью стека #4
нужно сделать конечный автомат
инфа и примеры:
Программа удаляющая все комментарии из листинга программы С++
Построить детерминированный конечный распознаватель

ещё рекурсивно проходить
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
16.09.2012, 10:55  [ТС]     Построить распознаватель языка с помощью стека #5
нет, рекурсивно ничего не проходиться, задача выложена и сделана, просто стек реализован на основе структур, а мне нада то же самое и принцип работы такой же, только мне нужно стек реализовать по другому, не структурами, а например через класс или еще как-нибудь
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
16.09.2012, 11:05     Построить распознаватель языка с помощью стека #6
Цитата Сообщение от sTARKj Посмотреть сообщение
4. <выр>::=<пер>|<оп1><выр>|<оп2><выр><выр>
это рекурсивная конструкция

подходящие цепочки:
+ A B
+ A + A B
+ A + корень B корень C
+ A + корень + B C D

Цитата Сообщение от sTARKj Посмотреть сообщение
нет, рекурсивно ничего не проходиться
да, скорее всего, из-за простоты хватит простого считывания по порядку
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
16.09.2012, 11:11  [ТС]     Построить распознаватель языка с помощью стека #7
Цитата Сообщение от accept Посмотреть сообщение
это рекурсивная конструкция

подходящие цепочки:
+ A B
+ A + A B
+ A + корень B корень C
+ A + корень + B C


да, скорее всего, из-за простоты хватит простого считывания по порядку
да, есть метод распознавания префикса с помощью рекурсии, препод говорил что строка будет читаться с начала тогда, но мне сказал сделать с и с использованием стека, её можно вот 2-мя вариантами как минимум...Рекурсия или Стек, в стек складываем буквы, при встрече знака +-*/ вытаскиваем оба и заменяем одним, как бы что произошла операция, если встречаем корень то просто пропускаем ничего не делаем...вот если выражение префиксное, в стеке должен будет в конце остаться один символ, он как бы результат, от всего выражение ведь должен быть результат, в противном случае если осталось больше тогда выражение не префиксное
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
17.09.2012, 01:51     Построить распознаватель языка с помощью стека #8
Цитата Сообщение от sTARKj Посмотреть сообщение
в стек складываем буквы, при встрече знака +-*/ вытаскиваем оба и заменяем одним, как бы что произошла операция, если встречаем корень то просто пропускаем ничего не делаем
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
17.09.2012, 16:26  [ТС]     Построить распознаватель языка с помощью стека #9
Цитата Сообщение от accept Посмотреть сообщение
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
ну значит наоборот, мне нада проверить на префикс)
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
18.09.2012, 10:21     Построить распознаватель языка с помощью стека #10
попробовал префиксное решение - получается больше десяти строк (всякие просмотры стека, ещё проверки "а хватает ли в нём элементов для просмотра")

может, действительно, надо переводить в постфиксную запись

Добавлено через 5 часов 20 минут
длинная форма
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <stdio.h>
 
int f(const char *p);
 
int main(void)
{
    const char *arr[] = {
        "A",
        "sA",
        "+AB",
        "*sA+sBsC",
        "AB",
        "s",
        "+A",
        "*sA+sB"
    };
    int i;
    
    for (i = 0; i < sizeof arr / sizeof arr[0]; i++)
        printf("%s %d\n", arr[i], f(arr[i]));
    return 0;
}
 
#include <string.h>
#include <ctype.h>
 
void push(int c);
int pop(void);
void clear(void);
int peek(int n);
int ssize(void);
 
/* 
  терминалы:
    A...Z    - переменная
    s        - операция корень (одноместная)
    + - * /  - одна из операций (двухместная)
  нетерминалы:
    '+'      - двухместная операция
    's'      - одноместная операция
    'A'      - операнд
 */
 
int f(const char *p)
{
    enum {
        START, /* начало/стек пуст */
        ANYOP, /* в стеке любая операция (одно- или двух-) */
        OP2A,  /* в стеке двухместная операция и операнд */
        A,     /* в стеке один операнд */
        END    /* выход при ошибке */
    } state;
    int c;
 
    clear();
    state = START;
    while ((c = *p) != '\0'
        && (state == START || state == ANYOP || state == OP2A)) {
        if (strchr("+-*/", c))
            push('+');
        else if (c == 's')
            push('s');
        else if (isupper(c))
            push('A');
        else
            state = END;
        if (state != END) {
            if (peek(1) == 'A') {
                while ((ssize() > 1 && peek(2) == 's')
                    || (ssize() > 2 && peek(2) == 'A' && peek(3) == '+')) {
                    if (peek(2) == 's') {
                        pop();
                        pop();
                        push('A');
                    } else {
                        pop();
                        pop();
                        pop();
                        push('A');
                    }
                }
            }
            if (peek(1) == '+' || peek(1) == 's')
                state = ANYOP;
            else if (peek(1) == 'A') {
                if (ssize() > 1 && peek(2) == '+')
                    state = OP2A;
                else
                    state = A;
            }
        }
        p++;
    }
    return c == '\0' && pop() == 'A' && ssize() == 0;
}
 
char stack[1000];
int spos = 0;
 
void push(int c)
{
    stack[spos++] = c;
}
 
int pop(void)
{
    return stack[--spos];
}
 
void clear(void)
{
    spos = 0;
}
 
int peek(int n)
{
    return stack[spos - n];
}
 
int ssize(void)
{
    return spos;
}
Код
[guest@localhost c]$ .ansi s.c -o s
[guest@localhost c]$ ./s
A 1
sA 1
+AB 1
*sA+sBsC 1
AB 0
s 0
+A 0
*sA+sB 0
[guest@localhost c]$
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
18.09.2012, 10:23  [ТС]     Построить распознаватель языка с помощью стека #11
Цитата Сообщение от accept Посмотреть сообщение
попробовал префиксное решение - получается больше десяти строк (всякие просмотры стека, ещё проверки "а хватает ли в нём элементов для просмотра")

может, действительно, надо переводить в постфиксную запись
короче ту что в начале кинул не совсем была верна, её доделали, а вот ещё сделали проверку на префикс на основе стека, только стек теперь реализован массивом char.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//---------------------------------------------------------------------------
 
#pragma hdrstop
#include<fstream.h>
#include<stdlib.h>
#include<string.h>
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<iomanip.h>
 
//---------------------------------------------------------------------------
 
#pragma argsused
int main(int argc, char* argv[], char *str)
{int i=0; char pr[20]; int k=0; bool w=false;
cout<<"Vvedite stroku: "<<endl;
cin>>str;
while(str[i]!=NULL)
{i++;}
if ((isalpha(str[0]))&&(str[1]==NULL))
cout<<"YES"<<endl;
if (isalpha(str[i-1]))
{{for(int j=i-1; j>=0; j--)
{if(isalpha(str[j]))
{pr[k]=str[j];
 k++;}
if ((str[j]=='+')||(str[j]=='-')||(str[j]=='/')||(str[j]=='*'))
{if ((isalpha(pr[0]))&&(pr[1]==NULL))
{cout<<"NOT"<<endl;
w=true;
break;
}
else
{pr[k-1]=NULL;
k--;}}}
}
if ((isalpha(pr[0]))&&(pr[1]==NULL)&&(w=false))
cout<<"YES"<<endl;}
else
cout<<"NOT"<<endl;
getch();
        return 0;
}
//---------------------------------------------------------------------------
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.09.2012, 07:17     Построить распознаватель языка с помощью стека #12
Цитата Сообщение от sTARKj Посмотреть сообщение
только стек теперь реализован массивом char
стек можно взять в C++, наверное

префиксная версия с лёгким стеком

Добавлено через 20 часов 47 минут
попробовал переписать это на C++ и через <stack>, и через <vector>
получился ещё больший код (неудобно там всё это делать)
нашёл ещё ошибку логическую у себя: при неправильном символе стек был пустой, но из него доставалось значение
исправленная версия
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
 
int f(const char *s);
 
int main(void)
{
    const char *arr[] = {
        "A",
        "sA",
        "+AB",
        "*sA+sBsC",
        "AB",
        "s",
        "+A",
        "*sA+sB",
        "x"
    };
    int i;
    
    for (i = 0; i < sizeof arr / sizeof arr[0]; i++)
        printf("%s %d\n", arr[i], f(arr[i]));
    return 0;
}
 
#include <string.h>
#include <ctype.h>
 
void push(int c);
int pop(void);
void clear(void);
int peek(int n);
int ssize(void);
 
/* 
  терминалы:
    A...Z    - переменная
    s        - операция корень (одноместная)
    + - * /  - одна из операций (двухместная)
  нетерминалы:
    '+'      - двухместная операция
    's'      - одноместная операция
    'A'      - операнд
 */
 
int f(const char *s)
{
    enum {
        START, /* начало/стек пуст */
        ANYOP, /* в стеке любая операция (одно- или двух-) */
        OP2A,  /* в стеке двухместная операция и операнд */
        A,     /* в стеке один операнд */
        END    /* выход при ошибке */
    } state;
    int c;
 
    clear();
    state = START;
    while ((c = *s) != '\0'
        && (state == START || state == ANYOP || state == OP2A)) {
        if (strchr("+-*/", c))
            push('+');
        else if (c == 's')
            push('s');
        else if (isupper(c))
            push('A');
        else
            state = END;
        if (state != END) {
            if (peek(1) == 'A') {
                while ((ssize() > 1 && peek(2) == 's')
                    || (ssize() > 2 && peek(2) == 'A' && peek(3) == '+')) {
                    if (peek(2) == 's') {
                        pop();
                        pop();
                        push('A');
                    } else {
                        pop();
                        pop();
                        pop();
                        push('A');
                    }
                }
            }
            if (peek(1) == '+' || peek(1) == 's')
                state = ANYOP;
            else if (peek(1) == 'A') {
                if (ssize() > 1)
                    state = (peek(2) == '+') ? OP2A : END;
                else
                    state = A;
            }
            s++;
        }
    }
    return c == '\0' && state == A;
}
 
char stack[1000];
int spos = 0;
 
void push(int c)
{
    stack[spos++] = c;
}
 
int pop(void)
{
    return stack[--spos];
}
 
void clear(void)
{
    spos = 0;
}
 
int peek(int n)
{
    return stack[spos - n];
}
 
int ssize(void)
{
    return spos;
}
Код
[guest@localhost c]$ .ansi s.c -o s
[guest@localhost c]$ ./s
A 1
sA 1
+AB 1
*sA+sBsC 1
AB 0
s 0
+A 0
*sA+sB 0
x 0
[guest@localhost c]$
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
29.10.2012, 05:25  [ТС]     Построить распознаватель языка с помощью стека #13
Цитата Сообщение от accept Посмотреть сообщение
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
Не просто читаем с конца строки вот и все...ну уже разобрались тут, спасибо всем большое.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2012, 20:53     Построить распознаватель языка с помощью стека
Еще ссылки по теме:

C++ Написать программу что меняло слово "кукушка" на "груша", с помощью стека
По русскому названию языка программирования определить английское название этого языка C++
C++ Распознаватель речи

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Deathcube
2 / 2 / 0
Регистрация: 29.12.2010
Сообщений: 13
15.11.2012, 20:53     Построить распознаватель языка с помощью стека #14
Здравствуйте! А есть такая задачка на паскале, и без стэка? Заранее благодарен!
Yandex
Объявления
15.11.2012, 20:53     Построить распознаватель языка с помощью стека
Ответ Создать тему
Опции темы

Текущее время: 09:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru