题目描述
给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。
数据可能会出现括号情况，还有可能出现多余括号情况。
数据保证不会出现大于或等于%2^{31}%的答案。
数据可能会出现负数情况。
输入格式
输入仅一行，即为表达式。
输出格式
输出仅一行，既为表达式算出的结果。
样例
输入样例：
(2+2)^(1+1)
输出样例：
16
这道题啊，特别坑，这些坑待会再讲，先讲这道题的基本思路:
定义两个栈： 一个字符栈， 一个数字栈，如下
然后就可以把原式经过转换存到这两个栈里面：
如果把运算符设成有优先度的运算符的话你就会明白了：
众所周知，×、÷、等二级运算比＋、—等以及运算优先度要大。
比如:
$$2+2 \times 2$$
这个算式，肯定是先算$2 \times 2 = 4$，所以原算式就变成了:
$$ 2 + 2 * 2 \\ = 2 + 4 \\ = 6 $$
但是再看看这个算式：
$$2 + 2 + 2$$
我们是不是也可以这样算:
$$2 + 2 + 2 = 2 + 4 = 6$$
所以我们在处理的时候可以这样做:
将加入的操作符和前面的每一个比较，如果栈顶运算符的优先级>=当前运算符的优先级，那么就把栈顶的运算符弹出，然后从数字栈里取两个数，然后把这两个数字用这个运算符算出来，比如我的数字栈里有2、2、3，然后我从字符栈里弹出来一个+号，于是就把2和3从栈里弹出来，2+3=5，于是再把这个5存进栈中。
就变成了：
数字栈：
2、5
。
存栈就这么存，上代码：
scanf("%s", s + 1);
int n = strlen(s + 1);
int num = 0;
for(int i = 1; i <= n; i++)
{
if(s[i] >= '0' && s[i] <= '9')
{
num = num * 10 + s[i] - '0';
flag = true;
}
else
{
// cout << flag << "*****" << num << endl;
if(flag)
{
flag = 0;
ints.push(num);
num = 0;
}
if(s[i] == '+')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '+' || chars.top() == '-' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '-')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '+' || chars.top() == '-' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '*')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '/')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '^')
{
while(!chars.empty() && chars.top() == '^')
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '(')
chars.push(s[i]);
if(s[i] == ')')
{
while(!chars.empty() && chars.top() != '(')
{
qwq(chars.top());
chars.pop();
}
if (!chars.empty()) chars.pop();
}
}
}
但是我这个qwq操作是神么呢？就是把从栈顶取出的运算符和这从数字栈里面取出的两个数字进行运算后再把它存会数字栈
void qwq(char ch)
{
int tt1 = ints.top();
ints.pop();
int tt2 = ints.top();
ints.pop();
// cout << tt2 << ch << tt1 << endl;
if(ch == '+')
{
ints.push(tt1 + tt2);
}
if(ch == '-')
{
ints.push(tt2 - tt1);
}
if(ch == '*')
{
ints.push(tt1 * tt2);
}
if(ch == '/')
{
ints.push(tt2 / tt1);
}
if(ch == '^')
{
ints.push(qpow(tt2, tt1));
}
}
但是这样肯定是不能过的，因为有两种特殊情况：
((((((-1)和(-1))))))
我们现在写的程序是过不了这两个数据的，因为我们的
代码并没有判断他是“负数”而非“A-B”的形态，所以就得写一个判断其是不是一个负数的代码：
if(s[i] == '-') {
if(!isdigit(s[i - 1]) && s[i - 1] != ')')
ints.push(0);
}
把这个代码加上就可以做出来了，完整代码:
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
bool flag;
char s[MAXN];
stack<char> chars;
stack<int> ints;
int tmp;
int qpow(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
template<typename T>
void print(stack<T> st) {
T *a = new T[st.size()];
cout << "size=" << st.size() << " --- ";
int i = 0;
while (!st.empty()) { a[i++] = st.top(); st.pop();
}
for (int j = i - 1; ~j; --j) cout << a[j] << " "; puts("");
delete a;
}
void qwq(char ch)
{
int tt1 = ints.top();
ints.pop();
int tt2 = ints.top();
ints.pop();
// cout << tt2 << ch << tt1 << endl;
if(ch == '+')
{
ints.push(tt1 + tt2);
}
if(ch == '-')
{
ints.push(tt2 - tt1);
}
if(ch == '*')
{
ints.push(tt1 * tt2);
}
if(ch == '/')
{
ints.push(tt2 / tt1);
}
if(ch == '^')
{
ints.push(qpow(tt2, tt1));
}
// print(ints);print(chars);
}
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
int num = 0;
for(int i = 1; i <= n; i++)
{
if(s[i] >= '0' && s[i] <= '9')
{
num = num * 10 + s[i] - '0';
flag = true;
}
else
{
if(s[i] == '-') {
// puts("???");
if(!isdigit(s[i - 1]) && s[i - 1] != ')')
ints.push(0);
}
// cout << flag << "*****" << num << endl;
if(flag)
{
flag = 0;
ints.push(num);
num = 0;
}
if(s[i] == '+')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '+' || chars.top() == '-' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '-')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '+' || chars.top() == '-' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
// print(ints); print(chars);
}
if(s[i] == '*')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '/')
{
while(!chars.empty() && (chars.top() == '*' || chars.top() == '/' || chars.top() == '^'))
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '^')
{
while(!chars.empty() && chars.top() == '^')
{
qwq(chars.top());
chars.pop();
}
chars.push(s[i]);
}
if(s[i] == '(')
chars.push(s[i]);
if(s[i] == ')')
{
// cout << chars.size() << " " << ints.size() << endl;
while(!chars.empty() && chars.top() != '(')
{
qwq(chars.top());
chars.pop();
}
if (!chars.empty()) chars.pop();
}
}
}
if (flag) ints.push(num);
while(!chars.empty() && chars.top() != '(')
{
qwq(chars.top());
chars.pop();
}
printf("%d\n", ints.top());
return 0;
}
嗯嗯，谢谢
判断优先级的代码可以开个hash表记录每种运算符的优先级, 这样可以少写很多if判断