VPF::[C++]Работа со стеком - Форум программистов

flow90

Дата 23.5.2007, 22:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 19.4.2007

Репутация: нет
Всего: нет

Задача вот такая:
Произвести проверку соблюдения баланса операторов CASE - END, BEGIN - END в тексте программы на языке Паскаль(в моем случае на языке С++). Использовать программный стек.

то есть переводя на язык С++, проверить выполнение баланса скобок { ( [.

в алгоритме ничего необычного...если встречаем одну из скобок, заносим ее в стэк, встречаем закрывающуюся -- удаляем ее оттуда...но вот с записью проблемы...первая задача со стэком, поэтому я не знаю как оно там вобще...
если кому несложно, расчитываю на вашу помощь...
thanks beforehand! smile

Anikmar

Дата 23.5.2007, 23:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Что я не могу понять - зачем тут нужен стек... Это обязательно?
Достаточно ведь три счетчика на каждый вид скобки
Встретили открывающую скобку - увеличили соответствующий счетчик, встретили закрывающую - уменьшили...

Что собственно в стек записывать? Позицию скобки? А потом выдавать попозиционно? Если нужен просто баланс скобок то не понимаю.

zkv

Дата 24.5.2007, 01:44 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Anikmar, ошибаетесь, стек тут самое оно smile

Код


#include <stack>     //использовал STL'вский стек, свой писать неохота :)
#include <fstream>
#include <iostream>

using std::cin;
using std::cout;

//проверяет баланс скобок в файле
bool CheckFile( const char *strFileName );

int main(int argc, char* argv[])
{
    if( CheckFile("main.cpp") )
        cout<<"\n main.cpp - good file";
    else
        cout<<"\n main.cpp - bad file";
    cin.get();
}

//проверяет баланс скобок в файле
bool CheckFile( const char *strFileName )
{
    std::stack<char> stkBrackets;
    std::ifstream fin( strFileName );
    if( !fin )
    {
        cout<<"\nCant open it";
        return false;
    }
    char cSym = 0;
    while( !fin.eof() )
    {
        fin.get( cSym );
        if( fin.eof() )//на всякий пожарный
            break;
        //развернул в один свитч, для наглядности
        switch( cSym )
        {
        case '{': 
        case '[':
        case '(': 
            cout<<"\n push "<<cSym;   //для демонстрации, можно убрать
            stkBrackets.push( cSym );
        break;
        case '}': 
            if( stkBrackets.top() == '{'  )
            {
                cout<<"\n pop "<<cSym;//для демонстрации, можно убрать
                stkBrackets.pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;//для демонстрации, можно убрать
                return false;
            }
        break;
        case ']':
            if( stkBrackets.top() == '['  )
            {
                cout<<"\n pop "<<cSym;//для демонстрации, можно убрать
                stkBrackets.pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;//для демонстрации, можно убрать
                return false;
            }
        break;
        case ')':
            if( stkBrackets.top() == '('  )
            {
                cout<<"\n pop "<<cSym;
                stkBrackets.pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;
                return false;
            }
        break;
        }
    }
    return stkBrackets.size() == 0;
}

flow90

Дата 24.5.2007, 18:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 19.4.2007

Репутация: нет
Всего: нет

zkv, спасибо большое!но вот проблема в том, что если я покажу на STL мне не поверят, так как мы его еще не начинали проходить, нельзя ли это как-нибудь без классов....?заранее благодарна...

asdf999

Дата 25.5.2007, 20:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 24.5.2007

Репутация: нет
Всего: нет

не у кого нет никаких предложений....?
мне просто аналогичная задача нужна)))

Это сообщение отредактировал(а) asdf999 - 25.5.2007, 20:16

zkv

Дата 26.5.2007, 03:10 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Код


#include <fstream>//для использования std::ifstream
#include <iostream>// -//- std::cin std::cout
//предупреждаем компилятор, что когда говорим cin, подразумеваем std::cin
//чтобы дальше не писать постоянно std::cin, а просто cin
using std::cin;
//тоже самое для cout
using std::cout;

//максимальный размер стека, если открывающих скобок встретится больше, 
//без соответствующих закрывающих будет плохо :)
#define MAX_SIZE_STACK 1000

//класс - стек символов
class CStack
{
//секция с зактрытами данными, доступ к ним имеют только методы этого 
//класса, по идее еще и друзья класса, но у нашего класса их нет :)
private:
//массив для хранения символов
    char m_pcBrackets[MAX_SIZE_STACK];
//текущий размер стека
    long m_lSize;
public:
//конструктор по умолчанию, вызывается при создании объекта
    CStack()
        :m_lSize(0)//при создании обнуляем размер стека
    {}
//метод добавляет символ в стек "сверху"
    void Push( char cSym )
    {
//добавляем символ, затем увеличиваем счетчик
        m_pcBrackets[ m_lSize++ ] = cSym;
    }
//метод убирает символ из стека "сверху"
    void Pop()
    {
//уменьшаем размер на 1
        if( m_lSize > 0 )
            --m_lSize;
    }
//метод возвращает "верхний" элемент в стеке
    char Top()
    {
        if( m_lSize > 0 )
            return m_pcBrackets[ m_lSize-1 ];
        else
            return 0;
    }
//метод возвращает текущий размер стека
    long Size()
    {
        return m_lSize;
    }
};
//проверяет баланс скобок в файле
bool CheckFile( const char *strFileName );

//главная функция приложения
int main(int argc, char* argv[])
{
//проверяем файл нашей функцией
    if( CheckFile("main.cpp") )
        cout<<"\n main.cpp - good file";
    else
        cout<<"\n main.cpp - bad file";
//ждем нажатия <Enter>
    cin.get();
}
//проверяет баланс скобок в файле
bool CheckFile( const char *strFileName )
{
    CStack stkBrackets;//создаем стек символов
    std::ifstream fin( strFileName );//открываем файл для чтения
    if( !fin )//если произошла ошибка, то говорим об этом
    {
        cout<<"\nCant open it";
        return false;
    }

    char cSym = 0; //сюду будем читать симвоы из файла
    while( !fin.eof() )//пока не настанет конец файла
    {
        fin.get( cSym );//берем символ из файла
        if( fin.eof() )//на всякий пожарный проверим не наступил ли конец
            break;

        //развернул в один свитч, для наглядности
        switch( cSym )//проверяем, что там у нас пришло
        {
        case '{': //если одна из открывающих скобок - добавляем ее в стек
        case '[':
        case '(': 
            cout<<"\n push "<<cSym;   //для демонстрации, можно убрать
            stkBrackets.Push( cSym );
        break;

//если одна из закрывающих, то смотрим, есть ли в стеке 
//соответствующая ей открывающая, если да - убираем ее (открывающую) из стека
        case '}': 
            if( stkBrackets.Top() == '{'  )
            {
                cout<<"\n pop "<<cSym;//для демонстрации, можно убрать
                stkBrackets.Pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;//для демонстрации, можно убрать
                return false;
            }
        break;

        case ']':
            if( stkBrackets.Top() == '['  )
            {
                cout<<"\n pop "<<cSym;//для демонстрации, можно убрать
                stkBrackets.Pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;//для демонстрации, можно убрать
                return false;
            }
        break;

        case ')':
            if( stkBrackets.Top() == '('  )
            {
                cout<<"\n pop "<<cSym;
                stkBrackets.Pop();
            }
            else
            {
                cout<<"\n Incorrect bracket:"<<cSym;
                return false;
            }
        break;

        }
    }
//в конце проверяем, чтобы в стеке не осталось открывающих скобок
    return stkBrackets.Size() == 0;
}

Исправил баги, добавил пару проверок, на компиляторе не могу сечас проверить, если что говорите smile

Это сообщение отредактировал(а) zkv - 27.5.2007, 14:35

apook

Дата 26.5.2007, 07:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23

Код


#include<ctype.h>
#include<conio.h>

#include<stdio.h>
#include<string.h>

#include<stdlib.h>


FILE *in;


//баланс скобок

long balance( int bracket )
{
int i, FLAG=-1, opposit;
long curpos=0, retcurpos=0;
curpos=ftell( in );

if( bracket==']' )
    opposit='[';
else if( bracket=='[' )
    opposit=']';

else if( bracket=='(' )
    opposit=')';
else if( bracket==')' )
    opposit='(';

else if( bracket=='{' )
    opposit='}';
else if( bracket=='}' )
    opposit='{';

else if( bracket=='|' )
    opposit='|';


fseek( in, -1L, SEEK_CUR );
for( i=curpos; i>=0; i-- )
{
    if( fgetc(in)==bracket )
    {
        FLAG=0;
        break;
        }
    fseek( in, -3L, SEEK_CUR );
    }

if( FLAG==0 )
    for( ; !feof(in); )
        if( fgetc(in)==opposit || feof(in) )
        {
            FLAG=1;
            break;  
            }

clearerr( in );
fseek( in, -1L, SEEK_CUR );

fseek( in, -1L, SEEK_CUR );
retcurpos=ftell(in);
fseek( in, curpos, SEEK_SET );

/*
FLAGS-value
-1-ошибка(ненайдена даже первая скобка)
0-найдена первая скобка но не найдена противоположная скобка
1-баланс соблюден
*/
return( FLAG<1 ) ? FLAG : retcurpos;
}


void block_where( long startblock, long endblock )
{
char *tmp, *p;
int ch, j, c,i;
long curpos;
curpos=ftell( in );

tmp=new char[ endblock-startblock ];

fseek( in, startblock, SEEK_SET );
for( i=0; !feof(in);  )
    if( (tmp[ i ]=fgetc(in))!=EOF && ftell(in)<endblock && !feof(in) )
        ++i;
tmp[ i ]='\0';

printf( "%s\n", tmp ); 

delete [] tmp;
clearerr( in );
fseek( in, endblock, SEEK_SET );
return;
}


//                        -|-||-||MAIN||-||-|-


void main( )
{
char buf[ 100 ];
int i, j, c, x;

in=fopen( ".\\Dummy.$$$", "r" );

if( !in )
    exit( 1 );

//ЧТЕНИЕ БЛОКОВ
fseek( in, 0L, SEEK_SET );
for( i=0; fgets(buf, 100, in); i++ )
{
    for( j=0; j<(signed)strlen( buf ); j++ )
    {
        if( buf[ j ]=='{' && ((x=balance('{')))>0 )
            block_where( ftell(in), x );
        }
    }

fcloseall();
return;
}

M
Guedda

Модератор: Пользуйтесь кнопкой "Код!"

Это сообщение отредактировал(а) Guedda - 27.5.2007, 14:42

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

asdf999

Дата 27.5.2007, 10:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 24.5.2007

Репутация: нет
Всего: нет

apook, спасибо smile

, но мне нужно с использованием стэка...

zkv, с классами я еще плоховато знаком, поэтому вот эту часть программы не понимаю...если вам несложно, можно туда комментариев... smile

спасибо)
flow90, у нас случайно не общие преподователи?))))вы откуда?

Код


class CStack
{
private:
    char m_pcBrackets[MAX_SIZE_STACK];
    long m_lSize;
    long m_lCurr;
public:
    CStack()
        :m_lSize(0),m_lCurr(0)
    {}

    void Push( char cSym )
    {
        m_pcBrackets[ ++m_lCurr ] = cSym;
    }

    void Pop()
    {
        --m_lCurr;
    }

    char Top()
    {
        return m_pcBrackets[ m_lCurr ];
    }

    long Size()
    {
        return m_lSize;
    }
};

Это сообщение отредактировал(а) asdf999 - 27.5.2007, 11:10

flow90

Дата 27.5.2007, 11:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 19.4.2007

Репутация: нет
Всего: нет

asdf999, очень врятли smile

я написала вам на ваш ящик.
а от комментариев я тоже не откажусь smile

Бонифаций

Дата 27.5.2007, 14:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 827
Регистрация: 15.9.2005
Где: Brisbane

Репутация: 1
Всего: 40

Цитата(zkv @ 24.5.2007, 01:44

)

ошибаетесь, стек тут самое оно

обработка комментариев и литералов? типа

Код



if ( test ) // ) ) )
{
  
cout << "  {  ";

}

Я уверен что такие задачи надо начинать с lex/flex и уже потом смотреть результаты лексического анализа

--------------------

Бонифаций.

zkv

Дата 27.5.2007, 14:44 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Бонифаций, это понятно, делаем скидку на то, что задача учебная, тем более есть уточнение:

Цитата(flow90 @ 23.5.2007, 22:39

)

в алгоритме ничего необычного...если встречаем одну из скобок, заносим ее в стэк, встречаем закрывающуюся -- удаляем ее оттуда...

тем более если есть проблемы с написанием даже такой программы, то с разбором комментариев будет сложнее.

flow90

Дата 27.5.2007, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 19.4.2007

Репутация: нет
Всего: нет

zkv, значит комментариев не будет...?

zkv

Дата 27.5.2007, 16:50 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

flow90, простите, забыл сказать, что исправил мой пост выше smile

flow90

Дата 28.5.2007, 14:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 19.4.2007

Репутация: нет
Всего: нет

zkv, спасибо большое!!!!!!!вы мне очень помогли!!!!!!! smile

F18

Дата 8.6.2008, 10:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 8.6.2008

Репутация: нет
Всего: нет

C++]:работа со стеком:
Задача вот такая:>>В текстовом файле записано без ошибок логическое выражение следующего вида:
<лог.выр.>::=true | false | !<лог.выр> | <лог.выр>.>&&<лог.выр> |<лог.выр.> || <лог.выр.>
Используя стек, вычислить значение этого выражения с учетом общепринятого приоритета операций.

я всю голову сломал помогите пожалуйста очень прошу

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »