题解：一本通1356 calc

2024-12-23

未分类

2.4k 词

I. 定义变量

Tip:
建议定义全局变量，可以自动初始化，不用担心之后进行类似“a++”等操作时出问题

stack <int> number; // 数字栈
stack <char> symbol; // 符号栈

string str; // 输入内容
int len, num; // 输入内容长度以及要入数字栈的数
bool flag = false; // 是否要将 要入数字栈的数 入栈

II. 读题

提炼有用信息：

“ 方程中只有$‘(’，‘)’，‘0-9’，‘+’，‘-’，‘*’，‘/’，‘^’$ ”

很多人会被这一句话和样例误解，以为是只有一位数，最后惨遭WA，但其实是有多位数的

“ 破密了Ferrari设的密码门 ”

Ferrari(music)

(music)I’m a Ferrari~~

(music)pulled off on Mulholland Drive~~

(music)Over the city, the lights are so pretty from up here~~~~~~

III. 解题思路构思

根据题意+样例，我们得知输入为 中缀表达式

所以我们有一下三种解题方式：

1.中缀转前缀后计算

2.中缀转后缀后计算

3.直接计算

因为茶叶的脑容量不够，想不到怎么转，所以我选择

直接计算

Tip:
因为输入没有空格，所以我们选择使用$string$类型输入，在输入后进行遍历操作

1 首先解决数字的入栈

因为数字是多位数，所以我们选择使用一个$int$类型变量$num$用来存储要入数字栈的数

当当前字符为数字字符时，将$num$的个位窜到百位，百位窜到千位，以此类推，使用num *= 10就可以轻松实现

当到达符号字符时说明数字已经结束，这个时候就可以将$num$入栈数字栈

==但怎么知道有数字要入栈呢？==

可以定义一个用来判断要不要将变量$num$入栈的$bool$变量：==$flag$==，在num *= 10的时候将$flag$设为$true$，在入栈后将$flag$设为$false$。这样一来，在到达符号字符时通过判断$flag$的值就可以知道该不该入栈了

*2 符号字符怎么办

*a. 是’(‘

当先遍历到的符号字符为 ==’(‘== 时，直接扔进符号栈就好了

*b. 是’)’

当当先遍历到的符号字符为 ==’)’== 时

因为括号里的运算等级更高，所以我们需要在遇到 ‘)’ 时马上计算括号内内容，只要没有到达 ‘(‘ 就一直计算，这个时候就体现出把 ‘(‘ push到符号栈里的作用了，用来计算括号内内容

但怎么计算

这个题目在这一步还是比较友善，因为所有的运算都需要两个数参与

所以我们可以先取到数字栈栈顶的两个数和符号栈栈顶的符号进行运算，运算过程直接判断符号运算就好

如何取栈顶示例：

1 2	int b = number.top(); // 取栈顶 number.pop(); // 出栈顶，这里出栈顶正好对应了我们要实现的计算完成后弹出符号/数字

因为计算需要反复使用，所以建议打包成函数方便以后使用

Tip:

注意注意注意数字栈栈顶两数的顺序！！！

栈：先入后出，后入先出

stack: first in last out, last in, first out

Tip2:
计算完括号内内容需要将符号栈栈顶出栈，因为此时的栈顶是 ‘(‘ ，如果留着会出大问题……

c. 理清逻辑

不要觉得普通是普通符号字符就可以直接进入符号栈


因为我们的数学还有优先级概念，所以我们需要先把优先级比当前符号字符高的符号计算完才能让它入栈

## 这里就到了茶叶坐牢的点！

首先我们需要知道**当前符号字符的优先级**和**栈顶符号的优先级**

我们根据尝试定下如下规则：

**BEST level**: 优先级为 $30$ 为最高级，是 ^(阶乘)

**MIDDLE level**: 优先级为 $20$ 为中间级，是 $*$ 和 $/$

**WORST level**: 优先级为 $10$ 为最拉级，是 $+$ 和 $-$

现在就可以通过战力值(优先级)来评定谁强谁拉了

**因为要重复使用，建议定义为一个函数**

**怎么真正实施计算呢？**

~~直接调用已经写好的计算函数啊！~~

计算战力值比当前符号字符高的强者拢共分三↑步

#### *① 比较优先级*

只要调用写好的函数就可以获得符号栈栈顶符号的优先级与当前符号字符的优先级，获得之后作比较就好力

****

**Tip:**
**记得用$while$，因为可能不止一个符号的优先级比当前符号的高**

****

#### *② 预防 $return$ $value$ $3221225477$ *
因为我们的计算函数中绝对会使用`栈名.pop()`，所以必须在外围的$while$循环中加入条件：`!symbol.empty()`

巧妙的是数字栈并不用担心这一点，因为从题意就可以得出**数字的个数绝对比符号的个数多，所以只要符号还有东西就一定有数字参加运算给你`pop`**

并且不用担心如果全是括号那数字不就比符号少了，因为我们前面已经筛掉了是括号的可能

### *d. 结束*

因为可能有些刁钻的测试样例会在所有运算结束后留下数字

所以需要在最后判断一下$flag$变量，如果$flag$变量为$true$，说明还有数残留，所以要把$num$入栈数字栈

因为刚刚可能有数字残留，但数字是要用来计算的，计算又是成双成对的，所以我们需要重新计算一下，但是并没有上面那么复杂，只要`while(!symbol.empty())`就好了，如果达成条件就调用计算函数就好了

最后输出`number.top()`，因为计算函数会将计算的值入栈数字栈，所以在最结尾时，`number.top()`就是结果

# 总结
# 自己理清思路后把所有写上就能AC

标签