思路:
1、初始化两个栈,操作数栈和运算符栈。实现代码中加入的小括号的匹配,注意题目并未要求。
2、若扫描到操作数,压入操作数栈。
3、若遇到小括号‘(’,直接入操作符栈,若遇到小括号‘)’,依次弹出操作符栈内的运算符,并每次弹出操作数栈的栈顶两个元素,计算后重新压入操作数栈,直至遇到小括号‘(’,弹出小括号‘(’。
4、若遇到运算符,依次弹出优先级高于或等于当前运算符的所有运算符,并每次弹出操作数栈的栈顶两个元素,计算后重新压入操作数栈。遇到小括号‘(’停止,之后再把当前运算符入操作符栈。
5、处理完字符串后。将操作符栈中的剩余运算符一次弹出,和上述计算方法一样。
6、最后操作数栈的栈顶元素即为字符串结果。
代码实现:
#include<iostream>
#include<string>
#include<stack>
using namespace std;
stack<int>num; //存放操作数
stack<char>ch; //存放操作符
//根据操作数和操作符计算并返回
int cal(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case 'x':
return a * b;
case '/':
return a / b;
}
}
//比较两个操作符的优先级,x1的优先级大于x2则返回0,否则返回1
int comp(char x1, char x2) {
if ((x1 == 'x' || x1 == '/') && (x2 == '+' || x2 == '-'))
return 0;
else
return 1;
}
//操作函数,取操作数栈的栈顶两元素和操作符的栈顶元素,计算后再入操作数栈
void opera(stack<int>& num, stack<char>& ch) {
int x1 = num.top();
num.pop();
int x2 = num.top();
num.pop();
char op = ch.top();
ch.pop();
num.push(cal(x2, x1, op));
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (auto& x : s) {
if (isdigit(x)) //操作数直接入栈
num.push(x - '0');
if (x == '(') //左括号直接入栈
ch.push(x);
if (x == '+' || x == '-' || x == 'x' || x == '/') { //操作符进行判断
while (!ch.empty() && ch.top() != '(' && comp(x, ch.top()) == 1) {
opera(num, ch);
}
ch.push(x);
}
if (x == ')') {
while (!ch.empty() && ch.top() != '(') {
opera(num, ch);
}
ch.pop();
}
}
while (!ch.empty()) { //字符串遍历完后,处理运算符栈中剩余操作符
opera(num, ch);
}
if (num.top() == 24)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
}