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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 5.00
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
29.03.2013, 09:01     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки) #1
Дано математическое выражение, к примеру {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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.03.2013, 09:01     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки)
Посмотрите здесь:

C++ Проверить, правильно ли расставлены скобки в выражении
Дана строка, содержащая латинские буквы и скобки. Если скобки расставлены правильно - вывести 0. Иначе - номер позиции, где есть ошибочная скобка C++
Проверить, правильно ли в текст входят круглые скобки. Ответ ДА или НЕТ с++ C++
C++ Нужен алгоритм, которым можно проверить, правильно ли пользователь расставил скобки
C++ Проверить, правильно ли в арифметическом выражении расставлены скобки.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11822 / 6801 / 769
Регистрация: 27.09.2012
Сообщений: 16,869
Записей в блоге: 2
Завершенные тесты: 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
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
29.03.2013, 09:43  [ТС]     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки) #3
большое спасибо))
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
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;
}
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
31.03.2013, 11:36  [ТС]     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки) #5
спасибо)
Croessmah
31.03.2013, 20:07     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки)
  #6

Не по теме:

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

Yandex
Объявления
31.03.2013, 20:07     Работа со стеком (Необходимо проверить,правильно ли расставлены скобки)
Ответ Создать тему
Опции темы

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