Stack

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns true if the string has balanced brackets: (), {}, []
5
bool isBalanced(const string &s) {
6
    stack<char> st;
7
    auto isOpen = [](char c){ return c=='(' || c=='{' || c=='['; };
8
    auto matches = [](char open, char close){
9
        return (open=='(' && close==')') ||
10
               (open=='{' && close=='}') ||
11
               (open=='[' && close==']');
12
    };
13
14
    for (char c : s) {
15
        if (isOpen(c)) {
16
            st.push(c);
17
        } else if (c==')' || c=='}' || c==']') {
18
            if (st.empty()) return false; // underflow: no opener to match
19
            char top = st.top(); st.pop();
20
            if (!matches(top, c)) return false; // mismatched types
21
        }
22
        // ignore other non-bracket characters if present
23
    }
24
    return st.empty(); // all openers must be matched
25
}
26
27
int main() {
28
    ios::sync_with_stdio(false);
29
    cin.tie(nullptr);
30
31
    // Example usage
32
    vector<string> tests = {
33
        "(a+b)*[c-{d/(e+f)}]",
34
        "([)]", // wrong nesting
35
        "((()))", // balanced
36
        "([{}])", // balanced
37
        "((]" // mismatch
38
    };
39
40
    for (const auto &t : tests) {
41
        cout << t << " -> " << (isBalanced(t) ? "Balanced" : "Not Balanced") << "\n";
42
    }
43
    return 0;
44
}
45

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int precedence(char op) {
5
    if (op == '+' || op == '-') return 1;
6
    if (op == '*' || op == '/') return 2;
7
    if (op == '^') return 3; // exponent (right-associative)
8
    return 0;
9
}
10
11
bool isRightAssociative(char op) {
12
    return op == '^';
13
}
14
15
// Convert infix expression with non-negative integers and operators +,-,*,/,^ and parentheses to postfix (tokens separated by spaces)
16
string infixToPostfix(const string &expr) {
17
    string out;
18
    stack<char> ops;
19
    int n = (int)expr.size();
20
    for (int i = 0; i < n; ) {
21
        if (isspace((unsigned char)expr[i])) { i++; continue; }
22
        if (isdigit((unsigned char)expr[i])) {
23
            // parse multi-digit number
24
            long long val = 0;
25
            while (i < n && isdigit((unsigned char)expr[i])) {
26
                val = val * 10 + (expr[i] - '0');
27
                i++;
28
            }
29
            out += to_string(val) + ' ';
30
        } else if (expr[i] == '(') {
31
            ops.push('(');
32
            i++;
33
        } else if (expr[i] == ')') {
34
            // pop until '('
35
            while (!ops.empty() && ops.top() != '(') {
36
                out += ops.top(); out += ' ';
37
                ops.pop();
38
            }
39
            if (!ops.empty() && ops.top() == '(') ops.pop();
40
            else throw runtime_error("Mismatched parentheses");
41
            i++;
42
        } else {
43
            // operator
44
            char op = expr[i++];
45
            int p = precedence(op);
46
            if (p == 0) throw runtime_error(string("Unknown token: ") + op);
47
            // pop while top has higher precedence, or equal and left-associative
48
            while (!ops.empty() && ops.top() != '(') {
49
                int pt = precedence(ops.top());
50
                if (pt > p || (pt == p && !isRightAssociative(op))) {
51
                    out += ops.top(); out += ' ';
52
                    ops.pop();
53
                } else break;
54
            }
55
            ops.push(op);
56
        }
57
    }
58
    // flush remaining operators
59
    while (!ops.empty()) {
60
        if (ops.top() == '(') throw runtime_error("Mismatched parentheses");
61
        out += ops.top(); out += ' ';
62
        ops.pop();
63
    }
64
    return out;
65
}
66
67
long long ipow(long long a, long long e) {
68
    long long res = 1;
69
    while (e > 0) {
70
        if (e & 1) res = res * a;
71
        a = a * a;
72
        e >>= 1;
73
    }
74
    return res;
75
}
76
77
// Evaluate postfix where tokens are space-separated numbers and operators +,-,*,/,^
78
long long evalPostfix(const string &postfix) {
79
    istringstream iss(postfix);
80
    stack<long long> st;
81
    string tok;
82
    while (iss >> tok) {
83
        if (tok.size() == 1 && string("+-*/^").find(tok[0]) != string::npos) {
84
            if (st.size() < 2) throw runtime_error("Insufficient operands");
85
            long long a = st.top(); st.pop();
86
            long long b = st.top(); st.pop();
87
            long long r = 0;
88
            switch (tok[0]) {
89
                case '+': r = b + a; break;
90
                case '-': r = b - a; break;
91
                case '*': r = b * a; break;
92
                case '/': if (a == 0) throw runtime_error("Division by zero"); r = b / a; break;
93
                case '^': if (a < 0) throw runtime_error("Negative exponent not supported"); r = ipow(b, a); break;
94
            }
95
            st.push(r);
96
        } else {
97
            // number token
98
            long long val = stoll(tok);
99
            st.push(val);
100
        }
101
    }
102
    if (st.size() != 1) throw runtime_error("Invalid postfix expression");
103
    return st.top();
104
}
105
106
int main() {
107
    ios::sync_with_stdio(false);
108
    cin.tie(nullptr);
109
110
    string expr;
111
    // Example input: (2 + 3) * 4 ^ 2 - 5
112
    getline(cin, expr);
113
    try {
114
        string post = infixToPostfix(expr);
115
        cout << "Postfix: " << post << "\n";
116
        cout << "Value: " << evalPostfix(post) << "\n";
117
    } catch (const exception &e) {
118
        cerr << "Error: " << e.what() << "\n";
119
    }
120
    return 0;
121
}
122

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Perform iterative DFS starting from 'src'. Returns visitation order.
5
vector<int> dfs_iterative(int n, const vector<vector<int>> &adj, int src) {
6
    vector<int> order;
7
    vector<char> vis(n+1, 0);
8
    stack<int> st;
9
    st.push(src);
10
    while (!st.empty()) {
11
        int u = st.top(); st.pop();
12
        if (vis[u]) continue; // guard duplicates
13
        vis[u] = 1;
14
        order.push_back(u);
15
        // Push neighbors; to mimic recursive DFS order (u->smallest first), push in reverse
16
        for (int i = (int)adj[u].size()-1; i >= 0; --i) {
17
            int v = adj[u][i];
18
            if (!vis[v]) st.push(v);
19
        }
20
    }
21
    return order;
22
}
23
24
int main() {
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
28
    int n, m; // number of vertices (1..n) and edges
29
    cin >> n >> m;
30
    vector<vector<int>> adj(n+1);
31
    for (int i = 0; i < m; ++i) {
32
        int u, v; cin >> u >> v;
33
        adj[u].push_back(v);
34
        adj[v].push_back(u); // make directed if needed by removing this line
35
    }
36
    for (int u = 1; u <= n; ++u) sort(adj[u].begin(), adj[u].end());
37
38
    int src = 1;
39
    vector<int> order = dfs_iterative(n, adj, src);
40
    for (int x : order) cout << x << ' ';
41
    cout << '\n';
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Next Greater Element (to the right). Returns indices of next greater (or -1).
5
vector<int> nextGreaterIndex(const vector<long long> &a) {
6
    int n = (int)a.size();
7
    vector<int> nge(n, -1);
8
    stack<int> st; // indices with decreasing values
9
    for (int i = 0; i < n; ++i) {
10
        while (!st.empty() && a[i] > a[st.top()]) {
11
            nge[st.top()] = i;
12
            st.pop();
13
        }
14
        st.push(i);
15
    }
16
    return nge;
17
}
18
19
// Largest Rectangle in Histogram using a monotonic (increasing) stack
20
long long largestRectangleArea(const vector<long long> &h) {
21
    int n = (int)h.size();
22
    vector<long long> heights = h;
23
    heights.push_back(0); // sentinel to flush the stack
24
    stack<int> st; // indices of increasing heights
25
    long long best = 0;
26
    for (int i = 0; i <= n; ++i) {
27
        long long cur = heights[i];
28
        while (!st.empty() && cur < heights[st.top()]) {
29
            long long height = heights[st.top()]; st.pop();
30
            int left = st.empty() ? -1 : st.top();
31
            int right = i; // first smaller to the right is i
32
            long long width = right - left - 1;
33
            best = max(best, height * width);
34
        }
35
        st.push(i);
36
    }
37
    return best;
38
}
39
40
int main() {
41
    ios::sync_with_stdio(false);
42
    cin.tie(nullptr);
43
44
    int n; cin >> n;
45
    vector<long long> a(n);
46
    for (int i = 0; i < n; ++i) cin >> a[i];
47
48
    vector<int> nge = nextGreaterIndex(a);
49
    cout << "Next Greater Element values (or -1):\n";
50
    for (int i = 0; i < n; ++i) {
51
        long long val = (nge[i] == -1 ? -1 : a[nge[i]]);
52
        cout << val << (i+1==n?'\n':' ');
53
    }
54
55
    int m; cin >> m;
56
    vector<long long> h(m);
57
    for (int i = 0; i < m; ++i) cin >> h[i];
58
    cout << "Largest Rectangle Area: " << largestRectangleArea(h) << "\n";
59
    return 0;
60
}
61