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

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

Войти
Регистрация
Восстановить пароль
 
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
#1

Работа со стеком (проверить правильность расстановки скобок) - C++

29.03.2013, 09:01. Просмотров 2756. Ответов 9
Метки нет (Все метки)

Дано математическое выражение, к примеру {x+(g-[f+h]*c)-(q+w)}.
Необходимо проверить,правильно ли расставлены скобки. Проверять следует следующим образом:если встретилась левая скобка,помещаем ее в стек. если правая,то сравниваем ее в верхним элементом стека,если скобки соответствуют, то удаляем ее из стека. Код написала,но в нем много синтаксических ошибок(первый раз работаю со стеком),не могу разобраться(((
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
#include <vcl.h>
#pragma hdrstop
#include <string.h>
#include <stdio.h>
#include <stack.h>
#pragma argsused
int main()
{
string s;
stack <string> st;
s="{x+(g-[f+h]*c)-(q+w)}";
printf("%s", s); // пыталась вывести строку на экран,но чего то не работает
for (int i=1;i<=s.size() ;i++)
{
if (s.substr(i,1)=="{" || s.substr(i,1)=="[" || s.substr(i,1)=="(")
st.push(s.substr(i,1));
if (s.substr(i,1)=="}" || s.substr(i,1)=="]" || s.substr(i,1)==")")
st.pop(s.substr(i,1));
}
if (st.empty()) printf("good");
else  printf("gbad");
getchar();
return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2013, 09:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Работа со стеком (проверить правильность расстановки скобок) (C++):

Проверить правильность расстановки скобок - C++
Помогите написать программу на c++. Дана строка, содержащая латинские буквы и скобки трех видов: «()», «», «{}». Если скобки расставлены...

Проверить правильность расстановки в тексте круглых скобок - C++
Задача: Проверить правильность расстановки в тексте круглых скобок. #include &lt;iostream&gt; #include &lt;cstring&gt; using namespace...

В символьной строке проверить правильность расстановки скобок - C++
Есть строка, нужно проверить её на правильное раставление скобок. Как это организовать правильно?

Проверить правильность расстановки в тексте круглых скобок (конечный автомат) - C++
Только начала изучать С++.Необходимо проверить правильность расстановки в тексте круглых скобок. Текст вводится с клавиатуры и...

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

Проверить в тексте файла правильность расстановки открывающих и закрывающих скобок - C++
Помогите, пожалуйста написать программу C++ Дан текстовый файл INPUT.TXT. Проверить в тексте файла правильности расстановки открывающих и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Croessmah
Эксперт CЭксперт С++
13207 / 7478 / 840
Регистрация: 27.09.2012
Сообщений: 18,388
Записей в блоге: 3
Завершенные тесты: 1
29.03.2013, 09:29 #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
37
#include "MTL_Stack.h"
#include <string>
#include <iostream>
#include <iomanip>
 
bool foo(std::string & sourcestr){
    std::string openstr="([{";
    std::string closestr=")]}";
    std::string::size_type pos_offset=0;
    MTL::Stack<std::string::size_type> st;
    for(std::string::iterator it=sourcestr.begin();it!=sourcestr.end();++it){
        if ((pos_offset=openstr.find(*it,0))!=std::string::npos){
            st.push(pos_offset);
        }else{
            if((pos_offset=closestr.find(*it,0))!=std::string::npos){
                if(st.empty()){
                    return false;
                }
                if(pos_offset==st.top()){
                    //Совпадение
                    st.pop();
                }else{
                    //Ожидается другая скобка
                    return false;
                }
            }
        }
    }
    return st.empty();
}
 
 
 
int main(){
    std::string sourcestr="[(2+2)*2+((2+4)+6)-[({}{}){}]]";
    std::cout<<std::boolalpha<<foo(sourcestr)<<std::endl;
}
MTL::Stack поменяйте на stack из STL
5
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
29.03.2013, 09:43  [ТС] #3
большое спасибо))
0
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
29.03.2013, 09:43 #4
Мне не очень нравится вариант с постоянным поиском подстроки. С учетом не слишком большого числа скобок, можно сделать отдельные вычисления или даже заинлайнить.
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
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
#include <stack>
 
bool isOpenBracket(char symbol) {
  return symbol == '(' || symbol == '{' || symbol == '[';
}
 
bool isClosingBracket(char symbol) {
  return symbol == ')' || symbol == '}' || symbol == ']';
}
 
char getOpenBracketPair(char bracket) {
  return (bracket == '}') ? '{' : (bracket == ')') ? '(' :
    (bracket == ']') ? '[' : '\0';
}
 
bool areParenthesesGood(const std::string &source) {
  std::stack<char> stack;
  for (size_t i = 0; i < source.size(); ++i) {
    if (isOpenBracket(source[i])) {
      stack.push(source[i]);
    } else {
      if (isClosingBracket(source[i])) {
        char openBracket = getOpenBracketPair(source[i]);
        if (!stack.empty() && stack.top() == openBracket) {
          stack.pop();
        } else {
          return false;
        }
      }
    }
  }
  return stack.empty();
}
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  std::string expression = "{x+(g-[f+h]*c)-(q+w)}";
  std::cout << areParenthesesGood(expression) << std::endl;
  
  std::cin.get();
  return 0;
}
4
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
31.03.2013, 11:36  [ТС] #5
спасибо)
0
Croessmah
31.03.2013, 20:07
  #6

Не по теме:

Цитата Сообщение от lemegeton Посмотреть сообщение
Мне не очень нравится вариант с постоянным поиском подстроки.
Ну как бы тогда достаточно в одном месте исправить искомые строки, например добавить еще какую-нибудь скобку для поиска, или удалить, а то и вообще передавать искомые скобки в функцию в качестве параметра

0
zarko97
276 / 36 / 0
Регистрация: 11.10.2015
Сообщений: 381
29.03.2017, 00:58 #7
как вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
bool isPosl(std::string& some)
{
    int brackets = 0;
    return (std::find_if(some.begin(), some.end(), [&brackets](char ch)
    {
        brackets += (ch == '(');
        brackets -= ((ch == ')') && (brackets > 0));
 
        return brackets == 0;
    }) != some.end()) ? true : false;
}
0
zarko97
276 / 36 / 0
Регистрация: 11.10.2015
Сообщений: 381
29.06.2017, 13:36 #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
 
int main() {
    
    std::string s = "[(2+2)*2+(2+4)+6)-[({}{}){}]]";
    
    int brackets = 0;
    for (char ch : s) {
        brackets += (ch == '(' || ch == '[' || ch == '{');
        brackets -= (ch == ')' || ch == ']' || ch == '}');
    }
    
    (brackets == 0) ? std::cout << "well" : std::cout << "ugly";
    
    return 0;
}
0
Croessmah
Эксперт CЭксперт С++
13207 / 7478 / 840
Регистрация: 27.09.2012
Сообщений: 18,388
Записей в блоге: 3
Завершенные тесты: 1
29.06.2017, 20:12 #9
zarko97, std::string s = "[)"; - получаем облом.
0
zarko97
276 / 36 / 0
Регистрация: 11.10.2015
Сообщений: 381
16.07.2017, 18:47 #10
Croessmah,
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
#include <iostream>
#include <string>
#include <map>
#include <stack>
 
std::map<char, char> brackets = {
    {')', '('},
    {'}', '{'},
    {']', '['}
};
 
inline bool open_brackets(char ch) {
    return ch == '(' || ch == '{' || ch == '[';
}
 
inline bool close_brackets(char ch) {
    return ch == ')' || ch == '}' || ch == ']';
}
 
bool good_sequence(std::string& str) 
{
    std::stack<char> st;
    for (auto ch : str) {
        if (open_brackets(ch)) st.push(ch);
        else if (close_brackets(ch)) {
            if (!st.empty() && st.top() == brackets[ch]) 
                st.pop();
            else 
                return false;
        }
    }
    return st.empty();
}
 
int main()
{
    std::string s = "([]))";
    (good_sequence(s)) ? std::cout << "yes" : std::cout << "no";
    system("pause");
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2017, 18:47
Привет! Вот еще темы с ответами:

Проверить правильность расстановки в тексте круглых скобок. Текст заканчивается точкой - C++
Работает,но неправильно. Сделала конечным автоматом. Помогите, пожалуйста! #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;cmath&gt; ...

Дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях - C++
дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях

Правильность расстановки скобок - C++
Всё обыскал но никак не могу найти именно то, что мне нужно, а именно: Со всем в принципе разобрался, только вот с ошибочными...

Написать рекурсивную функцию, проверяющую правильность расстановки круглых скобок в строке - C++
Написать рекурсивную функцию, проверяющую правильность расстановки круглых скобок в данной строке.


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

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

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