全面掌握信息学奥赛:计算(calc) 中的栈知识点
最编程
2024-02-04 15:10:46
...
1356:计算(calc)时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5797 通过数: 2252 【题目描述】小明在你的帮助下,破密了Ferrari设的密码门,正要往前走,突然又出现了一个密码门,门上有一个算式,其中只有“(”,“)”,“0-9”,“+”,“-”,“*”,“/”,“^”,求出的值就是密码。小明数学学得不好,还需你帮他的忙。(“/”用整数除法) 【输入】共1行,为一个算式。 【输出】共1行,就是密码。 【输入样例】 【输出样例】 提交 统计信息 提交记录 |
教学备忘录:编辑 |
无 |
给学生提示:编辑 |
无 |
中缀转后缀、计算后缀表达式
#include <iostream>
#include <cstdio>
#include <string>
#include <stack>
#include <cmath>
using namespace std;
stack <int> digit; // 数字栈
stack <char> symbol; // 符号栈
int level(char c) { // 判断符号的优先级
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
if (c == '^') return 3;
return 0;
}
void calculation() { // 将digit栈中最顶部两个数取出进行计算
int a = digit.top();
digit.pop();
int b = digit.top();
digit.pop();
char ch = symbol.top();
symbol.pop();
if (ch == '+') digit.push(a + b);
else if (ch == '-') digit.push(b - a); // 注意减法和除法a, b的顺序
else if (ch == '*') digit.push(a * b);
else if (ch == '/') digit.push(b / a);
else if (ch == '^') digit.push(pow(b, a));
}
int main()
{
string str;
cin >> str;
int len = str.length(); // 表达式长度
int x = 0;
bool tag = false; // 标记上一个字符是否为数字
for (int i = 0; i < len; i ++) {
if (str[i] >= '0' && str[i] <= '9') { // 处理多位数 注意会有大于十的数
x = x*10 + str[i]-'0';
tag = true;
}
else { // 此时字符不为数字
if (tag) { // 将数字入栈digit
digit.push(x);
tag = false;
x = 0;
}
if (str[i] == '(') { // 左括号就入栈symbol
symbol.push(str[i]);
continue;
}
if (str[i] == ')') { // 右括号就把左右括号之间的符号进行运算
while (symbol.top() != '(') {
calculation();
}
symbol.pop();
continue;
}
while (!symbol.empty() && level(symbol.top()) >= level(str[i])) { // 判断优先级
calculation(); // 此时符号优先级低于symbol栈顶元素的话 便进行计算
}
symbol.push(str[i]); // 优先级高的符号入栈
}
}
if (tag) { // 处理到最后会剩下一个数字 将其入栈
digit.push(x);
}
while (!symbol.empty()) { // 进行最后一步计算
calculation();
}
cout << digit.top() << endl; // digit栈中只有一个元素 即为表达式的结果
return 0;
}
无注释:
#include <iostream>
#include <cstdio>
#include <string>
#include <stack>
#include <cmath>
using namespace std;
stack <int> digit;
stack <char> symbol;
int level(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
if (c == '^') return 3;
return 0;
}
void calculation() {
int a = digit.top();
digit.pop();
int b = digit.top();
digit.pop();
char ch = symbol.top();
symbol.pop();
if (ch == '+') digit.push(a + b);
else if (ch == '-') digit.push(b - a);
else if (ch == '*') digit.push(a * b);
else if (ch == '/') digit.push(b / a);
else if (ch == '^') digit.push(pow(b, a));
}
int main()
{
string str;
cin >> str;
int len = str.length();
int x = 0;
bool tag = false;
for (int i = 0; i < len; i ++) {
if (str[i] >= '0' && str[i] <= '9') {
x = x*10 + str[i]-'0';
tag = true;
}
else {
if (tag) {
digit.push(x);
tag = false;
x = 0;
}
if (str[i] == '(') {
symbol.push(str[i]);
continue;
}
if (str[i] == ')') {
while (symbol.top() != '(') calculation();
symbol.pop();
continue;
}
while (!symbol.empty() && level(symbol.top()) >= level(str[i])) calculation();
symbol.push(str[i]);
}
}
if (tag) digit.push(x);
while (!symbol.empty()) calculation();
cout << digit.top() << endl;
return 0;
}