题目描述

输入一个表达式（用字符串表示），求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

输入：+3+2*{1+2*[-4/(8-6)+7]}

输出：25

 思路

使用两个栈来维护计算过程：一个数字栈，用来存储操作数字；一个操作符栈，用来存储‘+’,‘-’, ‘*’,‘/’ ,‘(’,‘)’,‘[’, ‘]’,‘{’ ,‘}’等操作符

如果当前运算符优先级('*/')高于栈顶运算符('+-')优先级，则将运算符入栈；反之，从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，符号栈压入当前运算符。重复该操作直到不满足条件。

出现左括号‘(’，则直接压入；出现右括号‘)’，则从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，重复该操作直到栈顶元素为左括号‘(’。

难点：

将数字从字符串中提取出来，而且要考虑正负号

运算符有优先级：有括号先算括号里的，再算乘除，最后加减，要满足从左往右运算顺序

注意：由于有除法运算，应该使用double格式来保存计算结果

使用到的字符串操作函数

find()与find_first_of()

string (1)

c-string (2)

buffer (3)

character (4)

size_t find (const string& str, size_t pos = 0) const noexcept;

size_t find (const char* s, size_t pos = 0) const;

size_t find (const char* s, size_t pos, size_type n) const;

size_t find (char c, size_t pos = 0) const noexcept;

string s = "hello world!";cout << s.find('o') << endl;//4cout << s.find('o', 5) << endl;//7cout << s.find("world") << endl;//6cout << s.find("word") << endl;//4294967295，未找到cout << s.find_first_of("word") << endl;//4,“wor” 出现在原字符串中，cout << s.find_last_of('o') << endl;//7

在当前字符串s中搜索传入参数字符串或者字符在s中首次出现的下标，与find_first_of()不同的是，find_first_of()找到了首个匹配的实例之后就不找了，就认定找寻成功，返回首个字符的下标，而find()则是要求完全匹配。如果输入了pos参数，则从下标pos开始查找。

查找失败：返回string::npos

static const size_t npos = -1; //npos is a static member constant value with the greatest possible value for an element of type size_t.

 npos是一个静态成员常量，其值为size_t类型的最大值：4294967295，用来表示没找到元素。

substr()

截取字符串

string substr (size_t pos = 0, size_t len = npos) const;

第一个参数pos是开始截取的位置下标，第二个参数len是截取的长度 ,若len==npos,意思是截取字符串从pos直到末尾

stoi()与stod()

将字符串转成int类型或double类型

实现代码

#include<iostream> #include<stack> #include<string> using namespace std; string nums = "0123456789"; //比较函数，用于比较当前操作符和栈顶操作符的优先级 //如果当前操作符优先级大于栈顶优先级，返回false //如果栈顶操作符为左括号( //如果当前操作符优先级小于栈顶优先级，true //还要满足从左往右计算顺序，如果当前操作符与栈顶操作符为同级关系，返回true //返回true说明此时需要将栈顶操作符弹出，用于计算 bool cmp(char top, char now){if(top == '('){return false;}else if((top == '-' || top == '+') && (now == '*' || now == '/')){return false;}return true; } //计算，从数字栈中弹出两个数字，操作符栈中弹出操作符 void calculate(stack<double> &num,stack<char> &op){ // 数字栈中数字的顺序也有要求 // 第一个弹出的数字在后面，第二个弹出的在前面double b = num.top();num.pop();double a = num.top();num.pop();char c = op.top();op.pop();if(c == '+') a = a+b;else if(c == '-') a = a-b;else if(c == '*') a = a*b;else if(c == '/') a = a/b;//将结果放入数字栈num.push(a);return ; } int main(void){string s;while(getline(cin, s)){//数字栈stack<double> num_stk;//操作符栈stack<char> op_stk;//预处理，将算式用括号括起来op_stk.push('(');s += ')';//算式的第一个应该是数字bool isNextOp = false;for(int i=0; i<s.size(); ++i){//左括号的话，直接压入操作符栈,将大中小括号都当做小括号处理if(s[i] == '(' || s[i] == '[' || s[i] == '{'){op_stk.push('(');}//右括号的话就可以开始计算，直到遇到与之对应的左括号else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){while(op_stk.top() != '(') //计算calculate(num_stk,op_stk);//弹出此时的（op_stk.pop();}//除括号外，数字和操作符应该是间隔排列的，而且算式的第一个应该是数字//若没有括号，需要考虑操作符优先级问题,并且是从左往右计算else if(isNextOp){while(cmp(op_stk.top(),s[i])){//计算calculate(num_stk,op_stk);}op_stk.push(s[i]);isNextOp = false;}//将数字从字符串中提取出来else{int j = i;//+ -符号可能是正负符号if(s[j] == '+' || s[j] == '-') ++i;//数字可能有多位，在0-9中while(nums.find(s[i]) != nums.npos) ++i;//i和j之间的字符即为数字//将数字提取，并压入数字栈//num_stk.push(stod(nums.substr(j,i-j)));num_stk.push((double)stoi(s.substr(j,i-j)));--i;//当前为数字，所以下一个为操作符isNextOp = true;}}//数字栈顶的元素即为最后结果cout<<num_stk.top()<<endl;}return 0; }

算法动图

算法动图制作方法

在网上经常看见别人写的算法图解动图，本以为有专门的软件可以用，但是没有找了一圈并没有发现这种软件。

网上的一些动图开源项目：

掘金

https://github.com/MisterBooo/Play-With-Sort-OC

于是自己决定采用土办法，使用PPT+录屏软件来制作算法动图：

发现一个很好用的gif录屏工具：screentogif

下载链接：ScreenToGif

首先在PPT中将算法步骤一张一张描绘出来，然后使用gif录屏软件制即可：

 当前算法PPT下载地址：

图解PPT

总结

以上是生活随笔为你收集整理的C++四则运算字符串解析（附动图以及动图制作方法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。