模拟栈

实现一个栈，栈初始为空，支持四种操作：

  1. push x – 向栈顶插入一个数 x；
  2. pop – 从栈顶弹出一个数；
  3. empty – 判断栈是否为空；
  4. query – 查询栈顶元素。

现在要对栈进行 M个操作，其中的每个操作 3和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤100000；
1≤x≤109；
所有操作保证合法。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

1
2
3
4
5
5
5
YES
4
NO

个人代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
class st {
	public:
		int a[N];
		int len = 0;
		int query() {
			return a[len - 1];
		}
		bool empty() {
			return len == 0;
		}
		int pop() {
			return a[--len];
		}
		void push(int x) {
			a[len++] = x;
		}
		void say() {
			for(int i=0;i<len;i++){
				printf("%d ",a[i]);
			}
		}
};
/*
	ps:尝试了c++类的编写，感觉萌萌哒
	push x – 向栈顶插入一个数 x
	pop – 从栈顶弹出一个数；
	empty – 判断栈是否为空；
	query – 查询栈顶元素。

*/
int main() {
	int n;cin>>n;
	st *now = new st();
	while(n--){
		string op;cin>>op;
		int val;
		if (op == "push") {
			cin>>val;
			now->push(val);
		} else if (op == "query") {
			cout<<now->query()<<endl;
		} else if (op == "empty") {
			string out;
			if (now -> empty()) {
				out = "YES";
			} else {
				out = "NO";
			}
			// 有些细节没有注意到导致出了些小问题
			cout<<out<<endl;
		} else {
			now->pop();
		}
	} 
}
/*
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty



*/

表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中，均不超过 2e31 − 1。
  • 题目中的整除是指向 00 取整，也就是说对于大于 0的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
  • C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

1
(2+2)*(1+1)

输出样例：

1
8

个人错误代码

1
人已经麻了，为啥为啥为啥！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
class st {
		int len = 0;
		string val[N];
	public:
		st() {

		}
		~st() {

		}
		string pop() {
			return val[--len];
		}
		string top() {
			return val[len - 1];
		}
		bool isD(string s) {
			if (s.size() > 1) {
				return s[1] <= '9' && s[1] >= '0';
			} else {
				return s[0] <= '9' && s[0] >= '0';
			}
		}

		bool isEmpty() {
			return len == 0;
		}
//		放置 一般数字 + - (
		void simPush(string s) {
			val[len++] = s;
		}
//		放置 ) 和 判断
		void push(string s) {
			if (s == ")") {
				int cur = 0;
				int f = atoi(this->pop().c_str());
				while (this->top() != "(") {
					string op = this->pop();
					if (op == "+") {
						cur = cur + f;
					}  else {
						cur = cur - f;
					}
					f = atoi(this->pop().c_str());
				}
				cur += f;
				this->pop();
				this->push(to_string(cur));
                //问题主要集中在这个位置我们需要理清楚这里已经没有*和除号了相当于对于除第一个数外的所有数增加了一个符号我们需要精确到对应得数值
			} else if (this->isD(s) &&
			           (this->len != 0 && (this-> top() == "*" || this->top() == "/") )) {
				int cur = atoi(s.c_str());
				if (this->top() == "*") {
					this->pop();
					int f = atoi(this->pop().c_str());
					cur = cur * f;
					this->simPush(to_string(cur));
				} else {
					this->pop();
					int f = atoi(this->pop().c_str());
					cur = f / cur;
					this->simPush(to_string(cur));
				}
			} else {
				this->simPush(s);
			}
		}
		int getVal() {
			int cur = atoi(this->val[0].c_str());
			for (int i = 1; i < len; i += 2) {
				string op = this->val[i];
				string val = this->val[i + 1];
				if (op == "+") {
					cur = cur + atoi(val.c_str());
				} else {
					cur = cur - atoi(val.c_str());
				}
			}
			return cur;
		}
		void say() {
			for(int i=0;i<len;i++){
				cout<<val[i]<<" ";
			}
			cout<<endl;
		}
};
int main() {
	st* res = new st();
	string s;
	cin >> s;
	int index = 0;
	while (index < s.size()) {
		string cur;
		cur += s[index++];
		while (index < s.size() && isdigit(s[index]) && isdigit(s[index - 1])) {
			cur += s[index++];
		}
		res->push(cur);
	}
	cout << res->getVal();
	
}

/*
	感悟：我也不知道为啥错了，我也很猛，但是我们知道了一些基本的东西比如 int 转化为 string 用
	to_string() 同时 string转int  atoi(val.c_str())

*/

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

/*
	感悟：做题得关键是抓到关键问题，首先我的关注点是在*,/,)上这不够抽象而题解关注于计算顺序当出现一个无法从后向前遍历得符号（当前的符号优先级小于上一个）便要求上一个先计算出结果让整个题目满足从后向前遍历的顺序。

*/