Simplify Path--LeetCode

左手的ㄟ右手 2022-08-07 11:43 7阅读 0赞

# 题目： #

Given an absolute path for a file (Unix-style), simplify it.

For example,  
path = `"/home/"`, => `"/home"`  
path = `"/a/./b/../../c/"`, => `"/c"`

[click to show corner cases.][]

Corner Cases:

*  Did you consider the case where path = `"/../"`?  
    In this case, you should return `"/"`.
 *  Another corner case is the path might contain multiple slashes `'/'` together, such as `"/home//foo/"`.  
    In this case, you should ignore redundant slashes and return `"/home/foo"`.

思路：使用栈辅助数据结构，来遍历整个字符串，注意在遍历字符串，根据当前字符和栈顶的字符来消除栈空间的内容，最后栈中留下的东西正好是最终的路径，不过觉得使用向量也非常合适

#include <iostream>
    #include <string>
    #include <vector>
    #include <stack>
     
    using namespace std;
    
    /*
    给一个Unix下面的路径表示方式 
    给出最终的结果 使用栈来消除复杂的表达方式 
    */
    string SimplifyPath(string& str)
    {
    	string result;
    	stack<char> st;
    	if(str.length() == 0 || str[0] !='/')
    		return result;
    	int i;
    	char tmp;
    	st.push(str[0]);
    	for(i=1;i<str.length();i++)
    	{
    		tmp = st.top();
    		if(isalpha(str[i])) //是字母 
    			st.push(str[i]);
    		if(str[i]=='/' && i!=str.length()-1)
    		{
    			if(tmp != '/' && tmp != '.') // 斜线 
    			{
    				st.push(str[i]);
    			}	
    			if(tmp == '.')
    			{
    				st.pop();
    			}
    		}
    		
    		if(str[i]=='.') //逗点 
    		{
    			if(tmp == '.')
    			{
    				st.pop();
    				st.pop();
    				if(!st.empty())
    					tmp = st.top();
    				while(!st.empty() && tmp != '/')
    				{
    					st.pop();
    					tmp = st.top();
    				}
    				if(st.empty())
    					st.push('/');
    			}
    			else
    				st.push(str[i]);
    		}
    	}
    	result.append(st.size(),'c');
    	i=st.size()-1;	
    	while(!st.empty())
    	{
    		tmp = st.top();
    		st.pop();
    		result[i--] = tmp;
    	}
    	
    	return result;
    } 
    int main()
    {
    	string str("/a/./b/../../c/");
    	//string str("/../");
    	cout<<SimplifyPath(str); 
    	return 0;
    }

[click to show corner cases.]: http://oj.leetcode.com/problems/simplify-path/#