CCF認證 201604-3 路徑解析
思路:一開始沒明白它什麼個意思,後來看了一下網上大佬的解法,就是判斷開始是否為/,後來對"." ".."進行處理。開始不為/或者為空就表示在目前目錄(一開始就給出)下進行處理。遇到一個點不用處理,兩個點表示上一級目錄。每當遇到/開始處理。
問題描述
在作業系統中,資料通常以檔案的形式存儲在檔案系統中。檔案系統一般采用階層化的組織形式,由目錄(或者檔案夾)和檔案構成,形成一棵樹的形狀。檔案有内容,用于存儲資料。目錄是容器,可包含檔案或其他目錄。同一個目錄下的所有檔案和目錄的名字各不相同,不同目錄下可以有名字相同的檔案或目錄。
為了指定檔案系統中的某個檔案,需要用路徑來定位。在類 Unix 系統(Linux、Max OS X、FreeBSD等)中,路徑由若幹部分構成,每個部分是一個目錄或者檔案的名字,相鄰兩個部分之間用 / 符号分隔。
有一個特殊的目錄被稱為根目錄,是整個檔案系統形成的這棵樹的根節點,用一個單獨的 / 符号表示。在作業系統中,有目前目錄的概念,表示使用者目前正在工作的目錄。根據出發點可以把路徑分為兩類:
絕對路徑:以 / 符号開頭,表示從根目錄開始建構的路徑。
相對路徑:不以 / 符号開頭,表示從目前目錄開始建構的路徑。
例如,有一個檔案系統的結構如下圖所示。在這個檔案系統中,有根目錄 / 和其他普通目錄 d1、d2、d3、d4,以及檔案 f1、f2、f3、f1、f4。其中,兩個 f1 是同名檔案,但在不同的目錄下。
對于 d4 目錄下的 f1 檔案,可以用絕對路徑 /d2/d4/f1 來指定。如果目前目錄是 /d2/d3,這個檔案也可以用相對路徑 ../d4/f1 來指定,這裡 .. 表示上一級目錄(注意,根目錄的上一級目錄是它本身)。還有 . 表示本目錄,例如 /d1/./f1 指定的就是 /d1/f1。注意,如果有多個連續的 / 出現,其效果等同于一個 /,例如 /d1///f1 指定的也是 /d1/f1。
本題會給出一些路徑,要求對于每個路徑,給出正規化以後的形式。一個路徑經過正規化操作後,其指定的檔案不變,但是會變成一個不包含 . 和 .. 的絕對路徑,且不包含連續多個 / 符号。如果一個路徑以 / 結尾,那麼它代表的一定是一個目錄,正規化操作要去掉結尾的 /。若這個路徑代表根目錄,則正規化操作的結果是 /。若路徑為空字元串,則正規化操作的結果是目前目錄。
輸入格式
第一行包含一個整數 P,表示需要進行正規化操作的路徑個數。
第二行包含一個字元串,表示目前目錄。
以下 P 行,每行包含一個字元串,表示需要進行正規化操作的路徑。
輸出格式
共 P 行,每行一個字元串,表示經過正規化操作後的路徑,順序與輸入對應。
樣例輸入
7
/d2/d3
/d2/d4/f1
../d4/f1
/d1/./f1
/d1///f1
/d1/
///
/d1/../../d2
樣例輸出
/d2/d4/f1
/d2/d4/f1
/d1/f1
/d1/f1
/d1
/
/d2
評測用例規模與約定
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
string fr[1000],se[1000];
int ff,ss;
int main()
{
int n;
string str,tmp;
cin>>n;
getchar();
cin>>str;
int len=str.size();
tmp="";ff=0;
for(int i=0;i<len;i++)
{
if(str[i]=='/')
{
if(tmp.size()==0) continue;
fr[ff++]=tmp;
tmp="";
}
else tmp+=str[i];
}
if(tmp.size()!=0) fr[ff++]=tmp;
getchar();
while(n--)
{
ss=0;
getline(cin,str);//給空的
//cin>>str;
int len=str.size();
if(len==0||str[0]!='/')
{
for(int i=0;i<ff;i++)
se[i]=fr[i];
ss=ff;
}
tmp="";
for(int i=0;i<len;i++)
{
if(str[i]=='/')
{
if(tmp.size()==0) continue;
else if(tmp==".");
else if(tmp=="..") ss==0?:ss--;
else se[ss++]=tmp;
tmp="";
}
else tmp+=str[i];
}
if(tmp.size()!=0)
{
if(tmp==".");
else if(tmp=="..") ss==0?:ss--;
else se[ss++]=tmp;
tmp="";
}
for(int i=0;i<ss;i++)
cout<<"/"<<se[i];
if(ss==0) printf("/");
printf("\n");
}
return 0;
}