1 / 1 / 0
Регистрация: 03.12.2010
Сообщений: 23
1

Задачка на стек

28.12.2011, 02:26. Показов 1124. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте. Есть такая задачка

Есть текст, сбалансированный по круглым скобкам.
Нужно вывести номера соответствующих открывающей и закрывающей скобок , упорядочив пары в порядке возрастания номеров позиций открывающих скобок.
пример : 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++;
};
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.12.2011, 02:26
Ответы с готовыми решениями:

Стек. Создать случайно генерированный стек и поменять местами первый элемент с i
Как создать случайно генерированный стек (тип элементов CHAR) и поменять местами первый элемент с i...

создать стек,заполнив числами 1,2,3...n.Посмотреть его содержимое,удалить стек
Всем привет!помогите,пожалуйста!!! создать стек,заполнив числами 1,2,3...n.Посмотреть его...

Заполнить очередь и стек и поменять их содержимое местами через дополнительный стек.
Необходимо разработать программу, которая должна : Заполнить очередь и стек и поменять их...

Используя стек, описать функцию проверяющую, является ли стек пустым
Используя стек, описать функцию проверяющую, является ли стек пустым

7
4744 / 2556 / 888
Регистрация: 29.11.2010
Сообщений: 5,525
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;
}
0
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;
}
К сожалению, мне нужно использовать модуль, который дал преподаватель. Так то я в поиске находил , но там по другому.
0
4744 / 2556 / 888
Регистрация: 29.11.2010
Сообщений: 5,525
28.12.2011, 03:29 4
Цитата Сообщение от tdu Посмотреть сообщение
К сожалению, мне нужно использовать модуль, который дал преподаватель. Так то я в поиске находил , но там по другому.
В чем сакральный смысл этого высказывания?
Ну перепиши тогда, используя этот загадочный "модуль". Я не могу его использовать, у меня его нет, и в поиске я не нашел "модуля, который дал преподаватель".
0
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
0
4744 / 2556 / 888
Регистрация: 29.11.2010
Сообщений: 5,525
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()
0
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
0
4744 / 2556 / 888
Регистрация: 29.11.2010
Сообщений: 5,525
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 Посмотреть сообщение
а мне нужно чтобы выводила в порядке возврастания позиций ОТКРЫВАЮЩИХ скобок, т.е вот так
Клади найденные пары цифр в стек, затем извлекай.

Вообще, этот порядок хорош тем, что это прямой порядок вычисления.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.12.2011, 20:43
Помогаю со студенческими работами здесь

Задачка с массивом и задачка с формулами Ньютона и Лагранжа
Прошу помочь решить две задачи

Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами ...

Описать и реализовать класс Стек, моделирующий массивом стек, для хранения любых объектов
ПОЖАЛУЙСТА ПОМОГИТЕ РАЗОБРАТЬСЯ С ЗАДАЧЕЙ НА JAVA!!! только начинаю изучать этот язык. буду очень...

Заполнить стек 20 случайными числами с интервала [0; -10]. Вывести стек на экран. Изъять из стека каждый четвертый элеме
Заполнить стек 20 случайными числами с интервала . Вывести стек на экран. Изъять из стека каждый...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru