栈知识点训练之计算(calc)

本文主要是介绍栈知识点训练之计算(calc)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述

【题目描述】

小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

【输入】

共1行，为一个算式。

【输出】

共1行，就是密码。

二、知识点考察

本题考察的是数据结构之栈的运用。可以使用C++ STL 内置的stack来解决此问题，使用stack需要引入对应的头文件：#include<stack>

三、解题思路

针对该题目，我们需要使用到两个栈，一个栈用来存储数值，不妨命名为values，另一个栈用来存储操作符，不妨命名为operators，针对不同的数据内容[数字或者运算符]，需要做不同的处理。

在这里，为了大家更方便理解，对输入输出样例进行一个模拟：

（1）准备两个栈，一个values，一个operators，针对样例数据，如下所示：

（2）计算规则如下

（3）计算过程模拟

有计算表达式如右：1+(3+2)*(7^2+6*9)/(2)，现按照以上计算规则进行计算过程模拟

① 从左往右遍历字符串，遇到数字1，将其放入values栈中

② 遇到运算符+，因为当前operators栈为空，因此直接将其放入operators栈中

③ 遇到运算符(，根据规则，直接将运算符(其放入operators栈中

④ 遇到数字3，根据规则，将数字入栈到values中

⑤ 遇到运算符+，根据规则，由于当前operators不为空，因此需要比较+和operators栈顶运算符的优先级，发现+的优先级高于(，因此将+入栈

⑥ 遇到数字2，根据规则，将数字入栈到values中

⑦ 遇到运算符)，根据规则，需要计算两个括号之间表达式的值，将结果放入values栈中，每次计算需要把values上面的两个数出栈，同时operators的一个运算符出栈

由于当前operators的栈顶已经是(了，因此计算结束，同时需要将栈顶的(出栈

⑧ 继续遍历字符串，遇到运算符*，由于operators栈不为空，因此需要比较operators栈顶运算符+和当前运算符*的优先级关系，发现*的优先级高于+，所以将运算符*入栈

⑨ 遇到运算符(，根据规则，直接将运算符(其放入operators栈中

⑩ 遇到数字7，根据规则，将数字入栈到values中

⑪ 继续遍历字符串，遇到运算符^，由于operators栈不为空，因此需要比较operators栈顶运算符(和当前运算符^的优先级关系，发现^的优先级高于(，所以将运算符^入栈

⑫ 遇到数字2，根据规则，将数字入栈到values中

⑬ 继续遍历字符串，遇到运算符+，由于operators栈不为空，因此需要比较operators栈顶运算符^和当前运算符+的优先级关系，发现^的优先级高于+，因此需要先对^进行计算，也就是计算7^2=49，将7、2、^出栈，49放入values栈中

+的优先级大于(，因此将刚刚的+放入operators栈中

⑭ 遇到数字6，根据规则，将数字入栈到values中

⑮ 继续遍历字符串，遇到运算符*，由于operators栈不为空，因此需要比较operators栈顶运算符+和当前运算符*的优先级关系，发现栈顶运算符+的优先级小于* ，因此*直接入栈

⑯ 遇到数字9，根据规则，将数字入栈到values中

⑰ 遇到运算符)，根据规则，需要计算两个括号之间表达式的值，将结果放入values栈中，将9、6出栈，*出栈，计算结果54放入values栈中

由于operators的栈顶运算符还不是(，因此继续计算：54、49、+出栈，计算结果54+49=103入栈，由于当前operators栈顶已经是(了，计算结束，同时将(出栈

⑱ 继续遍历字符串，遇到运算符/，由于operators栈不为空，因此需要比较operators栈顶运算符*和当前运算符/的优先级关系，发现当前运算符/的优先级不高于*号，因此先进行计算：103、5、*出栈，计算103*5=515,515放入values栈中

由于/的优先级高于栈顶的+，因此将/入栈，如下：

⑲ 遇到运算符(，根据规则，将其直接放入operators栈中，遇到数字2，将其直接放入values栈中

⑳ 遇到运算符)，由于现在栈顶元素是(，直接将其弹出即可

此时字符串已经遍历完毕，需要对栈内的数据进行运算，将515、2、/ 出栈，计算515/2=257，将257入栈，接着计算257、1、+出栈，计算257+1=258，将其入栈，由于operators栈已经空了，所以结果就是values栈顶的值258。

四、代码实现

学习了解题思路之后，我们就可以按照该思路来编写代码，我们主要代码思路分为三大部分，如下：

1、主程序

2、priority函数（主要用于返回操作符的优先级）

3、calculate函数（主要用于进行栈内数据的计算）

对于第一部分主程序而言，又可以进一步分为三个步骤：

1、读入字符串

2、根据规则进行对应的出入栈操作

3、输出结果

对于第二部分priority而言，可以进一步分为四个步骤：

1、如果操作符是+或者-，返回1

2、如果操作符是*或者/，返回2

3、如果操作符是^，返回3

4、其它返回0

对于第三部分calculate而言，可以进一步分为三个步骤：

1、从values栈中获取两个操作数

2、从operators栈中获取操作符

3、计算值，并将结果放入values栈

具体代码如下：

1、定义一个带有main函数的基本程序框架

2、定义priority函数(返回优先级)、calculate函数(计算数据)

3、保存数值的栈values、保存运算符的栈operators

4、定义代码中需要用到的相关变量

5、读入字符串、计算长度

6、遍历字符串，对运算符和数字进行操作，对于一个表达式而言，如果在处理的过程中遇到的一直是数字，那么则计算这些数字组成的数值

7、如果遇到运算符，需要先把之前计算的数字放入values栈中，然后判断当前遇到的是何种运算符，如果是(，则直接将其放入operators栈，如果是)，则计算()两边的表达式，且计算完毕后将(出栈。

8、如果operators栈为空，那么直接将运算符入栈，否则比较当前运算符和栈顶运算符的优先级，如果栈顶的优先级大于等于当前运算符的优先级，则调用calculate函数计算，否则将当前运算符直接入栈。

9、当字符串遍历完毕之后，如果最后一项是数字，则将其入栈，然后不断取出operators栈中的运算符进行运算，直到为空，最终values栈中只有一个数值，就是最终答案，取出输出即可。

接下来看一看priority函数和calculate函数的函数体内容：

五、完整参考代码

#include<bits/stdc++.h>
using namespace std;//保存数值 
stack<int> values;
//保存运算符 
stack<char> operators;//返回运算符优先级 
int priority(char c) {int ret = 0;switch(c) {case '+':case '-':ret = 1;break;case '*':case '/':ret = 2;break;case '^':ret = 3;break;}return ret;
}//计算数据结果 
void calculate() {int x = 0, y =0, result = 0;char op;y = values.top();values.pop();x = values.top();values.pop();op = operators.top();operators.pop();switch(op) {case '+':result = x+y;break;case '-':result = x-y;break;case '*':result = x*y;break;case '/':result = x/y;break;case '^':result = pow(x,y);break;}values.push(result);
}//定义一个带有main函数的基本程序框架
int main() {int value = 0;  //计算字符串当中的数值int len = 0;    //用于记录字符串长度int has_num = 0; //用来标记是否识别到数值char ch; //当前字符string chs; //当前字符串 cin >> chs;len = chs.length(); //遍历字符串for(int i=0;i<len;i++) {ch = chs[i];//如果遇到的一直是数字，则计算这些数字组成的数值if(isdigit(ch)) {value = value*10 + ch-'0';has_num = 1;}//不是数字，则是操作符 else {if(has_num) {values.push(value);value = 0;has_num = 0;}// ( 直接入栈 if(ch=='(') {operators.push(ch);continue;}if(ch==')') {while(operators.top()!='(') {calculate();}operators.pop();continue;} if(operators.empty()) {operators.push(ch);} else {while(!operators.empty()&&priority(operators.top())>=priority(ch)) {calculate();}operators.push(ch);}}} if(has_num) {values.push(value);}while(!operators.empty()) {calculate();}cout << values.top() << endl;return 0;
}