一些经典模拟题
计算器
对于「任何表达式」而言，都使用两个栈 nums 和 ops：
nums ： 存放所有的数字ops ：存放所有的数字以外的操作
从前往后遍历字符，分情况讨论：
- 空格 : 跳过（开始去除所有空格）
( : 直接加入 ops 中，等待与之匹配的 )) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums- 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入
nums
+ - * / ^ % : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算），使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算 是什么意思：
从前往后做，假设我们当前已经扫描到 2 + 1 了（此时栈内的操作为 + ）。
- 如果后面出现的
+ 2 或者 - 1 的话，满足「栈内运算符」比「当前运算符」优先级高/同等，可以将 2 + 1 算掉，把结果放到 nums 中；
- 如果后面出现的是
* 2 或者 / 1 的话，不满足「栈内运算符」比「当前运算符」优先级高/同等，这时候不能计算 2 + 1。
- 由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往
nums 添加一个 0
- 从理论上分析，
nums 最好存放的是 long，而不是 int，可能存在 中间结果溢出
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
| typedef long long ll;
class Solution {
private:
unordered_map<char, int> opMap = {{'+', 1}, {'-', 1}, {'*', 2},
{'/', 2}, {'%', 2}, {'^', 3}};
stack<ll> nums;
stack<char> ops;
void calc() {
if (nums.size() < 2 || ops.empty()) return;
ll b = nums.top();
nums.pop();
ll a = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
ll ans;
switch (op) {
case '+':
ans = a + b;
break;
case '-':
ans = a - b;
break;
case '*':
ans = a * b;
break;
case '/':
ans = a / b;
break;
case '%':
ans = a % b;
break;
case '^':
ans = pow(a, b);
break;
}
nums.push(ans);
}
public:
int calculate(string s) {
s.erase(remove(s.begin(), s.end(), ' '), s.end());
nums.push(0);
int n = s.size();
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == '(')
ops.push(c);
else if (c == ')') {
while (!ops.empty()) {
if (ops.top() == '(') {
ops.pop();
break;
}
calc();
}
} else {
if (c >= '0' && c <= '9') {
int num = 0, j;
for (j = i; j < n && s[j] >= '0' && s[j] <= '9'; j++)
num = num * 10 + (s[j] - '0');
nums.push(num);
i = j - 1;
} else {
if (i > 0 &&
(s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-'))
nums.push(0);
while (!ops.empty() && ops.top() != '(') {
if (opMap[ops.top()] < opMap[c]) break;
calc();
}
ops.push(c);
}
}
}
while (!ops.empty()) calc();
return nums.top();
}
};
|
大数运算
大数相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| string sum(string a,string b) {
if (a.size()<b.size())
swap(a,b);
int i,j;
for (i=a.size()-1,j=b.size()-1; i>=0; i--,j--) {
a[i]=(char)(a[i]+(j>=0?b[j]-'0':0));
if (a[i]-'0'>=10) {
a[i]=(char)((a[i]-'0')%10+'0');
if(i) a[i-1]++;
else a='1'+a;
}
}
return a;
}
|
大数相减
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
| string differ(string a,string b) {
int flag=0;
if (a.size()<b.size()) {
swap(a,b);
flag=1;
} else if (a.size()==b.size()) {
if (a<b) {
swap(a,b);
flag=1;
}
}
for (int i=a.size()-1,j=b.size()-1; i>=0; i--,j--) {
if (j>=0) b[i]=b[j];
else b[i]='0';
}
for (int i=a.size()-1; i>=0; i--) {
if (a[i]>=b[i])
a[i]=a[i]-b[i]+'0';
else {
a[i]=a[i]-b[i]+10+'0';
a[i-1]--;
}
}
while (a[0]=='0' && a.size()!=1) {
a.erase(0,1);
}
if (flag) a='-'+a;
return a;
}
|
大数相乘
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
| string product(string a, string b) {
string ans="0";
if (a.size()<b.size())
swap(a,b);
int cnt=-1;
for (int i=b.size()-1,j=a.size()-1; i>=0; i--){
int t=j;
string tmp;
int next=0;
while (t>=0){
int mid=(b[i]-'0')*(a[t]-'0')+next;
tmp=(char)(mid%10+'0')+tmp;
if (mid>=10)
next=mid/10;
else next=0;
t--;
}
if (next!=0) tmp=(char)(next+'0')+tmp;
cnt++;
for (int k=0; k<cnt; k++)
tmp=tmp+'0';
ans=sum(ans,tmp);
tmp.clear();
}
while (ans[0]=='0' && ans.size()!=1)
ans.erase(0,1);
return ans;
}
|