광의 표 의 수립 과 기본 조작

광의 표 의 수립 과 기본 조작

제목 정보

테스트 용례

해답

생각

제목 정보
'두미 법 으로 광의 표를 저장 하여 다음 과 같은 광의 표 의 조작 을 실현 한다. 1. Status CreateGList( GList &L, char *S ) / 문자열 S 가 표시 하 는 광의 표 내용 에 따라 광의 표 데이터 구 조 를 구축한다. 2. GList GetHead( GList L) / / 표 두 연산 3. GList GetTail( GList L) / 표 미 연산 4. void DestroyGList( GList &L) / 광의 표 L 5 를 없앤다. void PrintGList( GList L)/ / 광의 표 L 콘 텐 츠 프로그램 이 실 행 될 때 먼저 광의 표를 입력 하 십시오. 표 의 원 자 는 소문 자 입 니 다. 그 다음 에 표 의 머리 를 가 져 오 거나 표 의 끝 명령 을 가 져 올 수 있 습 니 다 (각각 1 과 2 로 표시). 가 져 온 결 과 는 현재 광의 표를 대체 하고 해당 하 는 자원 을 방출 할 수 있 습 니 다 (자원 정 보 를 출력 해 야 합 니 다).광의 표 가 비어 있 거나 원자 일 때 프로그램 이 실행 을 중단 합 니 다.
테스트 용례
테스트 용례 1

(a,(b,(c,d)),e,f)
2
1
2
1
1

generic list: (a,(b,(c,d)),e,f)
free head node
free list node
generic list: ((b,(c,d)),e,f)
destroy tail
free list node
generic list: (b,(c,d))
free head node
free list node
generic list: ((c,d))
destroy tail
free list node
generic list: (c,d)
destroy tail
free list node
generic list: c

테스트 용례 2

(a,(b,(c,(d,())),e))
2
1
2
1
2
1
2
1

generic list: (a,(b,(c,(d,())),e))
free head node
free list node
generic list: ((b,(c,(d,())),e))
destroy tail
free list node
generic list: (b,(c,(d,())),e)
free head node
free list node
generic list: ((c,(d,())),e)
destroy tail
free list node
generic list: (c,(d,()))
free head node
free list node
generic list: ((d,()))
destroy tail
free list node
generic list: (d,())
free head node
free list node
generic list: (())
destroy tail
free list node
generic list: ()

테스트 용례 3

((a,s,(w,e)),q,c)
1
2
2
2

generic list: ((a,s,(w,e)),q,c)
destroy tail
free list node
generic list: (a,s,(w,e))
free head node
free list node
generic list: (s,(w,e))
free head node
free list node
generic list: ((w,e))
free head node
free list node
generic list: ()

해답

#include
#include
#include 
#include 

using namespace std;

string Str;
int Point_1 = 0, Point_2;//        

void GetHead()
{
     
    cout << "destroy tail" << endl << "free list node" << endl << "generic list: ";
    int depth = -1;
    for (int i = Point_1; Str[i] != '\0'; i++)
    {
     
        if (Str[i] == '(')
        {
     //      (
            depth++;
            if (depth == 0)
                Point_1 = i + 1;
            continue;
        }
        if (Str[i] == ')')
        {
     //             `,` ，  `(`    `)`
            depth--;
            if (depth == 0)
            {
     
                Point_2 = i;
                break;
            }
            continue;
        }
        if (Str[i] == ',' && depth == 0)
        {
     //            ，      ，        ','   
            Point_2 = i - 1;
            break;
        }
    }
    for (int i = Point_1; i <= Point_2; i++)
        cout << Str[i];
    cout << endl;
}

void GetTail()
{
     
    cout << "free head node" << endl << "free list node" << endl << "generic list: ";

    int depth = -1;
    int Flag = 0;
    for (int i = Point_1; Str[i] != '\0'; i++)
    {
     
        if (i == Point_2)
        {
     //        ，       
            Flag = 1;
            break;
        }
        if (Str[i] == '(')
            depth++;
        if (Str[i] == ')')
            depth--;
        if (Str[i] == ',' && depth == 0)
        {
     //            ，    ，   
            Str[i] = '(';
            Point_1 = i;
            break;
        }
    }
    if (Flag == 1)
    {
     
        cout << "()" << endl;
        return;
    }
    for (int i = Point_1; i <= Point_2; i++)
        cout << Str[i];
    cout << endl;
}

int main()
{
     
    //freopen("/Users/zhj/Downloads/test.txt", "r", stdin);
    cin >> Str;
    cout << "generic list: " << Str << endl;
    Point_2 = Str.length() - 1;

    int op;
    while (cin >> op)
    {
     
        if (op == 1)
            GetHead();
        else
            GetTail();
    }
    return 0;
}

생각.
광의 표 ((a,b),c,d) 표 두 와 표 미 는 각각 무엇 입 니까? 공식: (1) 표 두: 광의 표 LS 가 비어 있 지 않 을 때 첫 번 째 요 소 를 LS 의 표 두 라 고 부 릅 니 다. (2) 표 미: 광의 표 LS 에서 표 두 를 제거 한 후에 나머지 요소 로 구 성 된 광의 표 는 LS 의 표 미 입 니 다. 아니면 표 두 와 표 미의 차 이 를 발견 하지 못 했 습 니까?! 표 두 는 원소 이 고 표 미 는 광의 표 입 니 다.!!
밤 광의 표 (a, (b)) 의 표 두 는 단원 소 a 이 고 표 미 는 광의 표 ((b)) 이다.
밤 을 하나 더 드 세 요.
밤 을 하나 더 들 어 라. 광의 표 (b) 의 표 두 는 단원 소 a 이 고 표 미 는 광의 표 ((b)) 이다.
자, 이제 알 겠 습 니 다. 광의 표 의 표 두 는 단일 요소 이 고 표 꼬리 는 광의 표 입 니 다.
요약: 광의 표 가 표 머리 와 표 꼬리 에 대한 정의 에 따라 알 수 있 듯 이 (1) 임의의 비 어 있 는 광의 표 에 대해 표 머리 는 단일 요소 일 수도 있 고 광의 표 일 수도 있 으 며 (2) 표 꼬리 는 반드시 광의 표 일 것 이다. (3) 표 꼬리 의 깊이 (즉 괄호 의 내장 층수) (4) 에 주의해 야 한다.표 미 는 표 두 를 제외 한 나머지 요소 로 구 성 된 광의 표 이기 때문에 표 꼬리 의 직접 요소 에 괄호 를 더 해 야 한다.
학습 이 어떤 지 검증 하기 위해 광의적 표 의 표 두 와 표 미 는 광의적 표 의 기본 적 인 조작 이다. 광의적 표 하 나 를 정 하면 특정한 요 소 를 표 두 와 표 미 를 통 해 구 할 수 있다. 광의적 표 (a) () () () ⑶ () (a, b, c) (b,c) ⑥ L=(a,(b,(c,(d)), e), f )이상 5 개가 맞다 면 광의 표 의 머리 와 끝 을 파악 한 것 을 축하합니다.
그 다음 에 조작 기법 을 살 펴 보 겠 습 니 다. 1. 다시 출력 해 야 하기 때문에 먼저 배열 로 저장 합 니 다. 2. 표 두 조작 을 통 해 두 개의 지침 인 P1, P2 를 만 들 고 각각 손가락 과 꼬리 에서 표 두 를 뽑 으 면 P1 이 첫 번 째 L1=Tail(L)=((b,(c,(d)), e), f ) 로 이동 한 후에 P2 는 현재 최대 괄호 의 첫 번 째 L2=Head(L1)= (b,(c,(d)), e) 로 이동 합 니 다. 예 를 들 어 원시 L3=Tail(L2)=((c,(d)), e), 표 두 를 뽑 으 면 P1 이 L4=Head(L3)=(c,(d)) 로 이동 하고 P2 는 L5=Head(L4)= c 로 이동 합 니 다.그 다음 에 P1 에서 P2 까지 출력 을 옮 겨 다 니 면 됩 니 다. 표 꼬리 작업 은 두 개의 지침 인 P1, P2 를 만 들 고 각각 손가락 과 꼬리 에서 표 꼬리 를 채취 하면 P1 이 첫 번 째 ( 에서 현재 최대 괄호 의 마지막 , 으로 이동 하 는 동시에 (a(b,c),d(e,),f) (a(b,c),d(e,),f) 으로 변 합 니 다. 만약 에 P1 이 P2 와 같 으 면 출력 (a(b,c),d(e,),f), 예 를 들 어 원시 (, 표 꼬리 를 채취 하면 P1 에서 , 로 이동 합 니 다.동시에 기 호 를 , 로 바 꾼 다음 에 P1 에서 P2 까지 출력 하면 어 려 운 점 이 있 습 니 다. ( 기호 등급 을 판단 하면 선령 () 이 만 나 는 것 (a,(b,c),e) 이 라면 (a,(b,c),e) "만 나 는 것 (a,(b,c)(e) 을 판단 하면 됩 니 다. 검색 을 할 때 이전 ”(“ , ”)” , ”,” 의 등급 을 판단 하면 됩 니 다. 우리 가 사용 해 야 할 등급 은 depth=-1, 즉 현재 최대 괄호 의 그것 입 니 다.