C++，LeetCode算法题的字符串输入处理

24. 算法

24.1. 二叉树输入处理，包括建树、打印树、释放树。

include<iostream>
#include <queue>
#include<sstream> //istringstream
using namespace std;

//结点
struct Node
{
    int val;
    Node* left;
    Node* right;

    Node() :val(0), left(nullptr), right(nullptr) {}; //空结点
    Node(int value):val(value), left(nullptr), right(nullptr) {}; //有值结点
};

//使用字符串流用于分割字符串
//建二叉树
Node* buildTree(istringstream& iss)
{
    string token="";
    if (!(iss >> token) || token == "null") return nullptr; //字符串流是空或者null时，直接返回空指针

    Node* root = new Node(stoi(token)); //新建根结点并入队
    queue<Node*>Q;
    Q.push(root);

    while (iss >> token) //新建当前节点的左右节点
    {
        Node* node = Q.front();
        Q.pop();

        if (token != "null")
        {
            node->left = new Node(stoi(token));
            Q.push(node->left);
        }

        if (!(iss >> token))
            break;

        if (token != "null")
        {
            node->right = new Node(stoi(token));
            Q.push(node->right);
        }

    }

    return root;
}

//释放二叉树
void deleteTree(Node* root)
{
    if (!root) return;

    deleteTree(root->left); //释放左子树
    deleteTree(root->right);//释放右子树

    delete root; //释放当前结点并置空
    root = nullptr;
}

//打印二叉树-层次遍历
void display(Node* root)
{
    if (!root) return;

    queue<Node*>Q;
    Q.push(root);

    while (!Q.empty())
    {
        int n = Q.size();
        while (n--)
        {
            auto node = Q.front();
            Q.pop();

            if (node) //如果结点存在，输出结点值并将左右结点入队
            {
                cout << node->val << " ";
                Q.push(node->left);
                Q.push(node->right);
            }
            else //如果结点不存在，输出null
                cout << "null ";
        }

        cout << endl; //一层一行
    }
       

}

int main()
{
    /*string s = "1 2 3 4 5 null 6 7 null null null null 8";*/
    string s;
    getline(cin, s); //控制台输入字符串

    istringstream iss(s); 
    Node* root = buildTree(iss); //建树

    display(root); //打印树
    
    deleteTree(root); //释放树
    return 0;
};

24.2. 单链表输入处理，包括建链（头插、尾插）、打印链、释放链。

istringstream 默认以空格作为分隔符来划分字符串，但可以使用 getline()指定分隔符。

#include<iostream>
#include<sstream>
using namespace std;

//结点
struct Node
{
    int val;
    Node* next;

    Node() :val(0), next(nullptr) {}; //空结点
    Node(int value):val(value), next(nullptr) {}; //有值结点，尾插
    Node(int value, Node* next):val(value),next(next){} //有值结点，头插
};

//建单链表-头插法
Node* insertHead(istringstream& iss)
{
    string token = "";
    if (!(getline(iss, token, ','))) return nullptr; //字符串流是空，直接返回空指针

    Node* head = new Node(stoi(token)); //新建第一个结点
    Node* cur = head;

    while (getline(iss, token, ',')) //新建其余结点
        cur = new Node(stoi(token),cur);

    return cur; //返回当前结点
}

//建单链表-尾插法
Node* insertTail(istringstream& iss)
{
    string token="";
    if (!(getline(iss,token,','))) return nullptr; //字符串流是空，直接返回空指针

    Node* head = new Node(stoi(token)); //新建第一个结点
    Node* cur = head;

    while (getline(iss, token, ',')) //新建其余结点
    {
        cur->next= new Node(stoi(token));
        cur = cur->next;
    }

    return head; //返回第一个结点
}

//释放单链表
void deleteList(Node* head)
{
    if (!head) return;

    while (head)
    {
        auto cur = head;
        head = head->next;

        delete cur; //释放结点并置空
        cur = nullptr;
    }
}

//打印单链表
void display(Node* head)
{
    if (!head) return;

    while (head)
    {
        cout<<head->val<<" ";
        head = head->next;
    }

    cout <<endl;
}


int main()
{
    /*string s = "[1,2,3,4]"*/
    string s;
    getline(cin, s); //控制台输入字符串

    s = s.substr(1, s.length() - 2); //去除首尾方括号

    istringstream iss(s);
    Node* head = insertTail(iss); //建链

    display(head); //打印链

    deleteList(head); //释放链
    return 0;
};

24.3. 一维矩阵输入处理。

#include<iostream>
#include <vector>
#include<sstream>
using namespace std;

int main()
{
    string s = "[1,2,3,4]";
    //string s;
    //getline(cin, s); //控制台输入字符串

    s = s.substr(1, s.length() - 2); //去除首尾方括号

    istringstream iss(s); 
    string token = "";
    vector<int>v;
    
    while (getline(iss, token, ','))//分割字符串并存放进数组
        v.emplace_back(stoi(token)); 
    
    for (auto&& u : v) //打印数组
        cout << u << " ";
       
    return 0;
};

24.4. 二维矩阵输入处理。

可以使用嵌套的 std::istringstream。

#include<iostream>
#include <vector>
#include<sstream>
using namespace std;

int main()
{
    string s = "[[1,3,5,7],[10,11,16,20],[23,30,34,60]]";
    //string s;
    //getline(cin, s); //控制台输入字符串

    s = s.substr(1, s.length() - 2); //去除首尾方括号

    istringstream iss(s);
    string token = "";
    vector<vector<int>>v;

    while (getline(iss, token, '[')) //以'['分割字符串，对应行
    {
        if (token.empty()) continue; //跳过空字符串

        istringstream in_iss(token);
        string in_token = "";
        vector<int>in_v;
		
		//如"7]"转7 是因为stoi()会提取开头的数字部分并将其转换为整数。
        while(getline(in_iss,in_token,',')) //以'，'分割字符串，对应列
            in_v.emplace_back(stoi(in_token));
        v.emplace_back(in_v); 
    }
        
    
    for (auto&& in_v : v) //打印二维数组
    {
        for (auto&& u : in_v)
            cout << u << " ";
        cout << endl;
    }

    return 0;
};

24.5. 调用函数输入处理。

最小栈，设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈，实现 MinStack 类。

#include<iostream>
#include<stack>
#include<vector>
#include<sstream>
using namespace std;

class MinStack {
private:
    stack<int>st,minst; //使用栈辅助检索最小元素

public:
    MinStack() { minst.push(INT_MAX); }

    void push(int val) {
        //当前元素-对应栈中最小元素
        if (val < minst.top())
            minst.push(val);
        else
            minst.push(minst.top());

        st.push(val);
    }

    void pop() {
        //同时出栈
        minst.pop();
        st.pop();
    }

    int top() { return st.top(); }
    
    int getMin() { return minst.top();}
};


int main()
{
    string scall = R"( ["MinStack","push","push","push","getMin","pop","top","getMin"] )"; //R"()"是一种原始字符串字面量的写法。
    string snum = "[[],[-2],[0],[-3],[],[],[],[]]";
    //string scall,snum;
    //getline(cin, scall); 
    //getline(cin,snum); //控制台输入字符串

    snum.erase(remove(snum.begin(), snum.end(), '['),snum.end()); 
    snum.erase(remove(snum.begin(), snum.end(), ']'), snum.end()); //snum去除'['和']'

    istringstream iss(snum);
    string token = "";
    vector<int>v;

    while (getline(iss, token, ',')) //snum以','分割字符串并存放进数组
    {
        if (token.empty()) continue; //跳过空字符串
        v.emplace_back(stoi(token)); 
    }

    scall = scall.substr(2, scall.length() - 4); //scall去除首"(["和尾"])"
    scall.erase(remove(scall.begin(), scall.end(), '"'), scall.end()); //scall去除'"'
    
    istringstream iss2(scall);
    int size = v.size(), i = 0;
    static MinStack minStack; //声明成静态，保证只初始化一次

    while (getline(iss2, token, ',')) //scall以','分割字符串并调用
    {
        if (token == "MinStack")
        {
            minStack = MinStack();
            cout << "null,";
        }
        else if (token == "push")
        {
            minStack.push(v[i++]);
            cout << "null,";
        }
        else if (token == "getMin")
        {
            cout << minStack.getMin() << ",";
        }
        else if (token == "pop")
        {
            minStack.pop();
            cout << "null,";
        }
        else if (token == "top")
        {
            cout<<minStack.top() << ",";
        }
    }

    return 0;
};