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

Задачка на стек - C++

Восстановить пароль Регистрация
 
tdu
1 / 1 / 0
Регистрация: 03.12.2010
Сообщений: 23
28.12.2011, 02:26     Задачка на стек #1
Здравствуйте. Есть такая задачка

Есть текст, сбалансированный по круглым скобкам.
Нужно вывести номера соответствующих открывающей и закрывающей скобок , упорядочив пары в порядке возрастания номеров позиций открывающих скобок.
пример : A + (45 - F (X) * (B - C))
вывести : 3 17; 8 10; 12 16
------------
Сам стек уже реализован, ну и функции работы с ним
1) push() - добавить в вершину стека
2) pop() - вытолкнуть верхний элемент из стека
3) top() - читать значение верхнего элемента.
так же функции isNull - проверка на конец и destroy разрушить стек.
Реализация стека и функции - правильные, нам их готовые дал преподаватель.

Не могу сообразить как правильно оформить алгоритм.
Вот мои мысли, с комментариями, которые может быть очень очевидны и глупы

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack s1, s2;
.
.
.
.
int i = 0;       // координата скобки
while (!s1.isNull())
    {
        if ( s1.top() == '(' )      
            {
                s2.push(i);   // заносим в стек s2 координату i открывающей скобки 
            }
        if ( s1.top() == ')' )   // если нашли закрывающую скобку
            {
                cout << s2.top()<<" " << i ;  // выводим координату откр. и закр. скобок
                                s2.pop(); // выдавливаем текущую координату из стека s2
                        }
        s1.pop();            // выдавливаем текущий элемент из стека s1
        i++;
};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 02:26     Задачка на стек
Посмотрите здесь:

C++ стек
C++ стек
C++ Стек
C++ Стек
C++ при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
28.12.2011, 03:20     Задачка на стек #2
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
#include <iostream>
#include <string>
#include <stack>
 
enum Brackets {
  LEFT_BRACKET = '(',
  RIGHT_BRACKET = ')'
};
 
struct Bracket {
  Bracket(Brackets bracket_, size_t position_)
    : bracket(bracket_), position(position_) {}
  Brackets bracket;
  size_t position;
};
 
int main(int argc, char *argv[]) {
  std::string expression = "A+(45-F(X)*(B-C))";
  std::stack<Bracket> stack;
  for (size_t i = 0; i < expression.size(); ++i)
    if (expression[i] == LEFT_BRACKET) {
      stack.push(Bracket(LEFT_BRACKET, i));
    } else
    if (expression[i] == RIGHT_BRACKET) {
      Bracket bracket(RIGHT_BRACKET, i);
      if (stack.empty()) {
        std::cout << "Error in expression." << std::endl;
        break;
      } else if (stack.top().bracket == LEFT_BRACKET) {
        std::cout << "[" << stack.top().position << ":" << i << "] ";
        stack.pop();
      }
    }
  if (!stack.empty())
    std::cout << "Error in expression." << std::endl;
}
tdu
1 / 1 / 0
Регистрация: 03.12.2010
Сообщений: 23
28.12.2011, 03:23  [ТС]     Задачка на стек #3
Цитата Сообщение от lemegeton Посмотреть сообщение
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
#include <iostream>
#include <string>
#include <stack>
 
enum Brackets {
  LEFT_BRACKET = '(',
  RIGHT_BRACKET = ')'
};
 
struct Bracket {
  Bracket(Brackets bracket_, size_t position_)
    : bracket(bracket_), position(position_) {}
  Brackets bracket;
  size_t position;
};
 
int main(int argc, char *argv[]) {
  std::string expression = "A+(45-F(X)*(B-C))";
  std::stack<Bracket> stack;
  for (size_t i = 0; i < expression.size(); ++i)
    if (expression[i] == LEFT_BRACKET) {
      stack.push(Bracket(LEFT_BRACKET, i));
    } else
    if (expression[i] == RIGHT_BRACKET) {
      Bracket bracket(RIGHT_BRACKET, i);
      if (stack.empty()) {
        std::cout << "Error in expression." << std::endl;
        break;
      } else if (stack.top().bracket == LEFT_BRACKET) {
        std::cout << "[" << stack.top().position << ":" << i << "] ";
        stack.pop();
      }
    }
  if (!stack.empty())
    std::cout << "Error in expression." << std::endl;
}
К сожалению, мне нужно использовать модуль, который дал преподаватель. Так то я в поиске находил , но там по другому.
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
28.12.2011, 03:29     Задачка на стек #4
Цитата Сообщение от tdu Посмотреть сообщение
К сожалению, мне нужно использовать модуль, который дал преподаватель. Так то я в поиске находил , но там по другому.
В чем сакральный смысл этого высказывания?
Ну перепиши тогда, используя этот загадочный "модуль". Я не могу его использовать, у меня его нет, и в поиске я не нашел "модуля, который дал преподаватель".
tdu
1 / 1 / 0
Регистрация: 03.12.2010
Сообщений: 23
28.12.2011, 03:39  [ТС]     Задачка на стек #5
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
// интерфейс АТД "Стек"
namespace st_modul
{
 
//-------------------------------------
    typedef char base;
    
    class Stack {
    struct node; 
 
    node *topOfStack;
 
    public:
        Stack ()
            { topOfStack = NULL;
            };
        base top (void);
        void pop (void);
        void push (const base &x);
        bool isNull(void);
        void destroy (void);
    };
 
 
}
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
// Implementation - Реализация АТД "Стек"
#include <iostream>
#include <fstream>
#include <cstdlib>
#include "st_interface.h"
using namespace std ;
 
namespace st_modul
{
    struct Stack::node {
    base *hd;
    node *tl;
        // constructor
        node ()
            {hd = NULL; tl = NULL; 
        }
    };// end node
 
//-------------------------------------
    base Stack::top (void) 
    {// PreCondition: not null  
        if (topOfStack == NULL) { cerr << "Error: top(null) \n"; exit(1); }
        else return *topOfStack->hd;
    }
//-------------------------------------
    void Stack::pop (void)
    {// PreCondition: not null
        if (topOfStack == NULL) { cerr << "Error: pop(null) \n"; exit(1); }
        else 
        {   node *oldTop = topOfStack;
            topOfStack = topOfStack->tl;
            delete oldTop->hd;
            delete oldTop;
        }
    }
//-------------------------------------
    void Stack::push (const base &x)
    {   node *p;
        p = topOfStack;
        topOfStack = new node; 
        if ( topOfStack != NULL)    {   
            topOfStack->hd = new base;
            *topOfStack->hd = x;
            topOfStack->tl = p;
        }
        else {cerr << "Memory not enough\n"; exit(1);}
    }
//-------------------------------------
    bool Stack::isNull(void)
    {   return (topOfStack == NULL) ;
    }
//-------------------------------------
    void Stack::destroy (void)
    {   while ( topOfStack != NULL) {
            pop();  
        }
    }
} // end of namespace h_list
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
29.12.2011, 18:23     Задачка на стек #6
Вот и замени стандартный объект std::stack на свой.

Объясняю популярно.
Вместо
C++
1
std::stack<Bracket>
надо
C++
1
st_modul::Stack
Вместо
C++
1
stack.empty()
надо
C++
1
stack.isNull()
Ну и у твоей реализации стека нет деструктора, поэтому в конце стек надо очистить.
C++
1
stack.destroy()
tdu
1 / 1 / 0
Регистрация: 03.12.2010
Сообщений: 23
30.12.2011, 02:00  [ТС]     Задачка на стек #7
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
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include "st_interface.h"
 
using namespace std;
using namespace st_modul;
 
enum Brackets {
  LEFT_BRACKET = '(',
  RIGHT_BRACKET = ')'
};
 
struct Bracket {
  Bracket(Brackets bracket_, size_t position_)
    : bracket(bracket_), position(position_) {}
  Brackets bracket;
  size_t position;
};
 
int main(int argc, char *argv[]) {
  std::string expression = "A+(45-F(X)*(B-C))";
  st_modul::Stack stack;
  for (size_t i = 0; i < expression.size(); ++i)
    if (expression[i] == LEFT_BRACKET) {
      stack.push(Bracket(LEFT_BRACKET, i));
    } else
    if (expression[i] == RIGHT_BRACKET) {
      Bracket bracket(RIGHT_BRACKET, i);
      if (stack.isNull()) {
        std::cout << "Error in expression." << std::endl;
        break;
      } else if (stack.top().bracket == LEFT_BRACKET) {
        std::cout << "[" << stack.top().position << ":" << i << "] ";
        stack.pop();
      }
    }
  if (!stack.isNull())
    std::cout << "Error in expression." << std::endl;
  stack.destroy();
 
}

Не прокатывает, выскакивают ошибки:

1>------ Построение начато: проект: 3, Конфигурация: Debug Win32 ------
1> st_main.cpp
1>.....\st_main.cpp(27): error C2664: st_modul::Stack:ush: невозможно преобразовать параметр 1 из "Bracket" в "const st_modul::base &"
1> Причина: невозможно преобразовать "Bracket" в "const st_modul::base"
1> Для выполнения данного преобразования нет доступного оператора преобразования, определенного пользователем, или вызов оператора невозможен
1>...\st_main.cpp(34): error C2228: выражение слева от ".bracket" должно представлять класс, структуру или объединение
1> тип: st_modul::base
1>...\st_main.cpp(35): error C2228: выражение слева от ".position" должно представлять класс, структуру или объединение
1> тип: st_modul::base
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========

Добавлено через 2 часа 47 минут
Я всё таки смог родить по своим мыслям, правда результат немножко некорректный.
Что у меня получается:

При выражении которое из первого сообщения A+(45-F(X)*(B-C))
программа выводит результат так : 8 10; 12 16; 3 17;
т.е., программа выводит номера скобок в порядке возврастания позиций ЗАКРЫВАЮЩИХ скобок,
а мне нужно чтобы выводила в порядке возврастания позиций ОТКРЫВАЮЩИХ скобок, т.е вот так :
3 17; 8 10; 12 16

Вот тут у меня начинается ступор, я не вижу простого решения, у меня складывается ощущение что всё надо совсем подругому реализовывать...

Вот что у меня получилось : ( смотреть , в принципе, стоит только первый кусок , т.к в нём алгоритм который видимо и работает немного не так как хотелось бы)

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
// ---st_main.cpp---
#include <iostream>
#include <fstream>
#include <string>
#include "st_interface.h"
 
using namespace std;
using namespace st_modul;
 
void solution(string str);      // прототипы
 
 
int main () 
{
    ifstream fin ("inputfile.txt");     
    string str;
    getline(fin, str);              // считываем выражение из inputfile.txt в строку str 
    cout << "exspression: "<< str << endl;
    fin.close();                // закрываем inputfile  
    solution (str);         //  вызываем void solution(string str);
    system("pause");
    return 0;
}
 
void solution (string str)
{
    Stack s1, s2;
    int i = 0;
    while ( i < str.size() ) 
    {
        if ( str[i] == '(' )
        { 
            s1.push(i+1);
        }
        if ( str[i] == ')' ) 
        {
            cout << s1.top() <<" "<< i+1 << "; ";
            s1.pop();
        }
        i++;
    }   
}
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
// st_interface.h
namespace st_modul
{
 
//-------------------------------------
    typedef int base;
    
    class Stack {
    struct node; 
 
    node *topOfStack;
 
    public:
        Stack ()
            { topOfStack = NULL;
            };
        base top (void);
        void pop (void);
        void push (const base &x);
        bool isNull(void);
        void destroy (void);
    };
 
 
}
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
// st_implementation.cpp
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include "st_interface.h"
using namespace std ;
 
namespace st_modul
{
    struct Stack::node {
    base *hd;
    node *tl;
        // constructor
        node ()
            {hd = NULL; tl = NULL; 
        }
    };// end node
 
//-------------------------------------
    base Stack::top (void) 
    {// PreCondition: not null  
        if (topOfStack == NULL) { cerr << "Error: top(null) \n"; exit(1); }
        else return *topOfStack->hd;
    }
//-------------------------------------
    void Stack::pop (void)
    {// PreCondition: not null
        if (topOfStack == NULL) { cerr << "Error: pop(null) \n"; exit(1); }
        else 
        {   node *oldTop = topOfStack;
            topOfStack = topOfStack->tl;
            delete oldTop->hd;
            delete oldTop;
        }
    }
//-------------------------------------
    void Stack::push (const base &x)
    {   node *p;
        p = topOfStack;
        topOfStack = new node; 
        if ( topOfStack != NULL)    {   
            topOfStack->hd = new base;
            *topOfStack->hd = x;
            topOfStack->tl = p;
        }
        else {cerr << "Memory not enough\n"; exit(1);}
    }
//-------------------------------------
    bool Stack::isNull(void)
    {   return (topOfStack == NULL) ;
    }
//-------------------------------------
    void Stack::destroy (void)
    {   while ( topOfStack != NULL) {
            pop();  
        }
    }
} // end of namespace h_list
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2011, 20:43     Задачка на стек
Еще ссылки по теме:

C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
Структура стек (: добавить элемент в стек, удалить элемент из стека, получить значение с вершины стека, размер стека...) C++
Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++

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

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
30.12.2011, 20:43     Задачка на стек #8
Цитата Сообщение от tdu Посмотреть сообщение
if ( str[i] == ')' ) {
cout << s1.top() <<" "<< i+1 << "; ";
s1.pop();
}
Тут надо проверить на корректность. Есть ли в стеке открывающая скобка.
C++
1
2
3
4
if (s1.isNull()) {
  std::cout << "Error in expression." << std::endl;
  break;
}
Цитата Сообщение от tdu Посмотреть сообщение
т.е., программа выводит номера скобок в порядке возврастания позиций ЗАКРЫВАЮЩИХ скобок
Да, именно так.
Цитата Сообщение от tdu Посмотреть сообщение
а мне нужно чтобы выводила в порядке возврастания позиций ОТКРЫВАЮЩИХ скобок, т.е вот так
Клади найденные пары цифр в стек, затем извлекай.

Вообще, этот порядок хорош тем, что это прямой порядок вычисления.
Yandex
Объявления
30.12.2011, 20:43     Задачка на стек
Ответ Создать тему
Опции темы

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