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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
#1

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

10.09.2012, 17:41. Просмотров 1534. Ответов 13
Метки нет (Все метки)

Приветствую, преподаватель задал задачку, сказал решение маленькое, порядка строк 8-10. Сам не очень программирую, есть предложения с чего начать?


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

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

Построить детерминированный конечный распознаватель - C++
Всем привет) у меня проблема, завтра надо курсач сдавать, у меня есть готовая лаба другого варианта, как переделать не знаю, помогите...

Реализация стека с помощью массива - C++
Извиняюсь. Неправильно тему назвал :) Стек – KStack Методы: конструкторы, деструктор; операции: &gt;&gt;, &lt;&lt;, +, +=, =, ==, != ...

Ошибки при реализации стека с помощью указателей - C++
Нужно написать программу реализующую стек с помощью указателей, прототипы функций даны. Написал ,но куча ошибок . Помогите пожалуйста , что...

Реализация бинарного древа с помощью рекурсии чревата переполнением стека? - C++
В реализации бинарного древа с помощью рекурсии (использования рекурсии в процессе написании функций бинарного древа) черевато...

С помощью языка программирования С++ разработать тестовую оболочку - C++
Как с помощью языка программирования С++ разработать тестовую оболочку? Пожалуйста помогите...

Написать программу,которая вычисляет значение арифметического выражения записанного в постфиксной форме,с помощью стека - C++
Написать программу,которая вычисляет значение арифметического выражения записанного в постфиксной форме,с помощью стека.Выражение...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kidasov
77 / 77 / 12
Регистрация: 02.12.2011
Сообщений: 965
Записей в блоге: 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;
}
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;
}
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
16.09.2012, 10:43 #4
нужно сделать конечный автомат
инфа и примеры:
Программа удаляющая все комментарии из листинга программы С++
Построить детерминированный конечный распознаватель

ещё рекурсивно проходить
0
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
16.09.2012, 10:55  [ТС] #5
нет, рекурсивно ничего не проходиться, задача выложена и сделана, просто стек реализован на основе структур, а мне нада то же самое и принцип работы такой же, только мне нужно стек реализовать по другому, не структурами, а например через класс или еще как-нибудь
0
accept
4822 / 3243 / 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 Посмотреть сообщение
нет, рекурсивно ничего не проходиться
да, скорее всего, из-за простоты хватит простого считывания по порядку
0
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-мя вариантами как минимум...Рекурсия или Стек, в стек складываем буквы, при встрече знака +-*/ вытаскиваем оба и заменяем одним, как бы что произошла операция, если встречаем корень то просто пропускаем ничего не делаем...вот если выражение префиксное, в стеке должен будет в конце остаться один символ, он как бы результат, от всего выражение ведь должен быть результат, в противном случае если осталось больше тогда выражение не префиксное
0
accept
4822 / 3243 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
17.09.2012, 01:51 #8
Цитата Сообщение от sTARKj Посмотреть сообщение
в стек складываем буквы, при встрече знака +-*/ вытаскиваем оба и заменяем одним, как бы что произошла операция, если встречаем корень то просто пропускаем ничего не делаем
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
0
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
17.09.2012, 16:26  [ТС] #9
Цитата Сообщение от accept Посмотреть сообщение
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
ну значит наоборот, мне нада проверить на префикс)
0
accept
4822 / 3243 / 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]$
0
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;
}
//---------------------------------------------------------------------------
0
accept
4822 / 3243 / 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]$
0
sTARKj
0 / 0 / 1
Регистрация: 10.09.2012
Сообщений: 40
29.10.2012, 05:25  [ТС] #13
Цитата Сообщение от accept Посмотреть сообщение
это ты описываешь постфиксную запись, а у тебя по заданию - префиксная
ты не можешь встретить знак, когда его операнды есть в стеке
Не просто читаем с конца строки вот и все...ну уже разобрались тут, спасибо всем большое.
0
Deathcube
2 / 2 / 0
Регистрация: 29.12.2010
Сообщений: 13
15.11.2012, 20:53 #14
Здравствуйте! А есть такая задачка на паскале, и без стэка? Заранее благодарен!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2012, 20:53
Привет! Вот еще темы с ответами:

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

Структура стек (: добавить элемент в стек, удалить элемент из стека, получить значение с вершины стека, размер стека...) - C++
Всем привет,ребят помогите пожалуйста с лабой,вообще без понятия про стеки:( Может кто то делал,или встречался с таким заданием: ...

Распознаватель речи - C++
Здравствуйте! Хочу написать программу в которой нужно будет преобразовывать звук в текст и делать с ним определенные действия. Для...

Написать программу что меняло слово "кукушка" на "груша", с помощью стека - C++
Написать программу что меняло слово кукушка на груша , с помощью стека(1 программа) и очередь(2 программа) Помогите пожалуйста очень...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.11.2012, 20:53
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru