华为机试

记录两个与栈相关的算法题，折腾了一下午

• 需要注意dfs前后对称的操作
• 利用栈结构去处理存在明显先后顺序的问题，比如四则运算等

HJ77 火车进站

栈+dfs回溯

#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> res;
vector<int> path;
void dfs(stack<int>& st, int index, vector<int >& nums) {
    if (index == N && st.empty()) {
        res.push_back(path);
        return;
    }
    // 进栈
    int tmp = nums[index];
    if (index < nums.size()) {
        st.push(tmp);
        dfs(st, index + 1, nums);
        st.pop();
    }
    // 出栈
    if (!st.empty()) {
        path.push_back(st.top());
        st.pop();
        dfs(st, index, nums);
        st.push(path.back());
        path.pop_back();
    }
}

int main() {

    cin >> N;
    vector<int > nums(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    stack<int> out;
    dfs(out, 0, nums);
    sort(res.begin(), res.end(), [](vector<int> a, vector<int> b) {
        for(int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return true;
    });

    for (auto v : res) {
        for (auto s : v)
            cout << s << " ";
        cout << endl;
    }
    return 0;
}

HJ50 四则运算

栈

#include <bits/stdc++.h>
using namespace std;

// 比较当前操作符和栈顶操作符优先级，cur<top 返回true
bool cmp(char cur, char top) {
    if (top == '(')
        return false;
    else if ( (cur == '*' || cur == '/') && (top == '+' || top == '-') )
        return false;
    return true;
}

void calc(stack<double> &num,stack<char> &op){
    int b=num.top();num.pop();
    int a=num.top();num.pop();
    char c=op.top();op.pop();
    if(c=='+') a=a+b;
    else if(c=='-') a=a-b;
    else if (c=='*') a=a*b;
    else if(c=='/') a=a/b;
    num.push(a);
}

double eval(string s){
    stack<double> num;
    stack<char> op;
    op.push('(');
    s+=")";
    bool isNextOp=false;
    for(int i=0;i<s.size();++i){
        // 判断括号
        if(s[i]=='('||s[i]=='['||s[i]=='{'){
            op.push('(');
            continue;
        }
        if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
            while(op.top()!='(')
                calc(num,op);
            op.pop();  //弹出 '('
            continue;
        }
        // 当下一个是数，不是op
        if(!isNextOp){
            int k=i;
            if(s[i]=='+'||s[i]=='-') i++;
            while(s[i]>='0'&&s[i]<='9') i++;
            double tmp=static_cast<double> (stoi(s.substr(k,i-k)));
            num.push(tmp);
            i--;
            isNextOp=true;
        }else{// 执行内部优先级
            while(cmp(s[i],op.top())){
                calc(num,op);
            }
            op.push(s[i]);
            isNextOp=false;
        }
    }
    return num.top();
}

int main() {
    string s;
    getline(cin, s);
    cout << eval(s);
    return 0;
}