2-4 栈操作的合法性

分数 6

作者 DS课程组

单位浙江大学

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式:

输入第一行给出两个正整数 n 和 m，其中 n 是待测序列的个数，m（≤50）是堆栈的最大容量。随后 n 行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式:

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

解析

#include <iostream>
#include <string>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		int count = 0;
		bool valid = true;

		for (char c : s) {
			if (c == 'S') {
				if (count == m) {
					valid = false;
					break;
				}
				count++;
			}
			else if (c == 'X') {
				if (count == 0) {
					valid = false;
					break;
				}
				count--;
			}
		}
		if (valid && count != 0) {
			valid = false;
		}
		cout << (valid ? "YES" : "NO") << endl;
	}
	return 0;
}

2-5 逆波兰表达式求值

分数 6

作者李廷元

单位中国民用航空飞行学院

逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（1 + 2）*（5 + 4），改为逆波兰表示法之后则是1 2 + 5 4 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

请输出以逆波兰表示法输入的算式的计算结果。

输入格式:

在一行中输入1个算式。相邻的符号（操作数或运算符）用1个空格隔开。

输出格式:

在一行中输出计算结果。

限制:

2≤算式中操作数的总数≤100

1≤算式中运算符的总数≤99

运算符仅包括“+”、“-”、“*”，操作数、计算过程中的值以及最终的计算结果均在int范围内。

输入样例1:

4 3 + 2 -

输出样例1:

输入样例2:

1 2 + 3 4 - *

输出样例2:

-3

解析

#include <iostream>
#include <string>
#include <stack>
#include <cctype> // 用于isdigit函数
using namespace std;

int stringtoint(const string& s) {
	int num = 0;
	int sign = 1;
	int start = 0;

	if (s[0] == '-') {
		sign = -1;
		start = 1;
	}

	for (int i = start; i < s.length(); i++) {
		num = num * 10 + (s[i] - '0');
	}
	return sign * num;
}

int main() {
	string input;
	getline(cin, input);

	stack<int> st;

	string current = "";

	for (int i = 0; i < input.length(); i++) {
		char c = input[i];
		if (c == ' ') {// 如果遇到空格，处理当前current
			if (current.empty() != 1) {
				if (current == "+" || current == "-" || current == "*") {
					int right = st.top();
					st.pop();
					int left = st.top();
					st.pop();
					if (current == "+") {
						int result = left + right;
						st.push(result);
					}
					else if (current == "-") {
						int result = left - right;
						st.push(result);
					}
					else if (current == "*") {
						int result = left * right;
						st.push(result);
					}
				}
				else {// 如果是操作数
					st.push(stringtoint(current));
				}
				current = "";
			}
		}
		else {
			current += c;
		}
	}

	if (!current.empty()) {
		if (current == "+" || current == "-" || current == "*") {
			int right = st.top(); 
			st.pop();
			int left = st.top();
			st.pop();

			if (current == "+") {
				st.push(left + right);
			}
			else if (current == "-") {
				st.push(left - right);
			}
			else if (current == "*") {
				st.push(left * right);
			}
		}
		else {
			st.push(stringtoint(current));
		}
	}

	cout << st.top() << endl;
	return 0;
}

注意

这个代码可以实现碰到两位数之类的数字，将字符串转换成int类型