返回主文件夾所需的最少操作數

給定一個陣列的串 的常用3 []表示在文件系統上執行的文件夾的操作的變化（Unix風格）。最初，文件系統在主文件夾中打開。該任務是查找以下三種類型的最小操作數以返回到主文件夾：

• “ ../”：移動到當前文件夾的父文件夾。（如果當前文件夾是主文件夾，則它將保留在同一文件夾中）。
• “ ./”：保留在同一文件夾中。
• “ F /”：移動到名為F的子文件夾。

例子：

    輸入： arr[] = {“F1/”, “F2/”, “./”, “F3/”, “../”, “F31/”}
    輸出： 3
    說明：
    arr[0] = “F1/”。移到名為F1的子文件夾。因此，當前目錄的路徑為/ F1。
    arr [1] =“F2/”。移到名為F2的子文件夾。因此，當前目錄的路徑為/ F1 / F2
    arr [2] =“./”。保留在當前文件夾中。因此，當前目錄的路徑為/ F1 / F2
    arr [3] =“F3/”。移到名為F3的子文件夾。因此，當前目錄的路徑為/ F1 / F2 / F3
    arr [4] =“../”。移至F3的父文件夾。因此，當前目錄的路徑為/ F1 / F2
    arr [5] =“F31 /”。移到名為F31的子文件夾。因此，當前目錄的路徑為/ F1 / F2 / F31
    現在，需要執行三次“ ../”操作才能返回到主文件夾。
    因此，所需的輸出為3。

    輸入： arr [] = {“ F1 /”，“ ../”，“ ../”}
    輸出： 0
    說明：
    arr [0] =“F1/”。因此，當前目錄的路徑為/ F1。
    arr [1] =“../”。因此，當前目錄的路徑為/
    arr [2] =“../”。因此，當前目錄的路徑為/。
    由於目錄的當前路徑已在主文件夾中，因此不需要任何操作。因此，所需的輸出為0。

方法：可以使用Stack解決該問題。請按照以下步驟解決問題：

1. 初始化一個變量，例如cntOp，以存儲返回主文件夾所需的最少操作數。
2. 創建一個堆棧，說st來存儲當前文件夾的路徑
3. 遍歷數組並檢查以下條件：
   如果arr [i] ==“ ../”，則彈出堆棧的頂部元素。
   如果arr [i] ==“ F /”，則將arr [i]的值壓入堆棧頂部。
4. 最後，打印留在堆棧中的元素計數。

下面是上述方法的實現：

// C++ program to implement 
// the above approach 
#include <bits/stdc++.h> 
using namespace std; 

// Function to find minimum number of 
// operations to go back to main folder 
int minOperations(vector<string>& arr, 
                            int N) 
{ 
    // Stores path of 
    // the current folder 
    stack<string> st; 

    for (int i = 0; i < N; i++) { 

        // If stack is not empty and 
        // the value of arr[i] is "../" 
        if (arr[i] == "../" && 
                    !st.empty()) { 

            // Pop top element of 
            // the stack             
            st.pop(); 
        } 

        // If the value of arr[i] 
        // is like "F/" 
        else if (arr[i] != "./") { 

            // Push arr[i] on top element 
            // of the stack             
            st.push(arr[i]); 
        } 
    } 

    // Return count of elements left 
    // into the stack 
    return st.size(); 
} 

// Driver Code 
int main() 
{ 
    vector<string> arr 
        = { "F1/", "F2/", "./", 
        "F3/", "../", "F31/" }; 
    int N = arr.size(); 
    cout << minOperations(arr, N); 
} 

輸出：

3

時間複雜度： O（N）
輔助空間： O（N）