当初抱着总结所学的想法,硬着头皮写了几篇博客。东拼西凑,理解的不够深刻,再加上写博客不够熟练导致再复盘的时候大多数的注意力放在了怎么写上面,而忽视了应该怎样写,写出来要表达一些什么东西,写完之后学到了哪些东西,最终还是在学习中发现了这样的问题,也停止了一段时间去思考该如何利用博客。通过近期的刷题,我逐渐发现了写题练习知识点只是一个十分的机械的过程,而真正带来飞跃的进步是思维上的锻炼,思维上的提升。所以我决定将博客当作我的一个学生,我将提炼出知识的精华尝试去教会他
适用场景
- 给出一个中缀表达式求出它的值
输出样例
(2+2)*(1+1)
处理数字
给出一个字符串,我们要提取其中的数字部分。
char c = str[i]; // i 表示遍历总字符串的位置,c表示当前位置字符,为了干净所以定义c
if(isdigit(c))
{
int x = 0, j = i; // x 用来存储这一段数字字符串的值,比如"12"转换为12
while(j < str.size() && isdigit(str[j]))
x = x * 10 + str[j ++] - '0'; // j 不断后移直至找到非字符停止
i = j - 1; // i在总遍历循环后会自增,如果不等于i - 1 会跳过一个非数字字符
num.push(x);// 最后将x放入存储结构中
}
处理括号
略过,明白意思即可, 后面会给出
处理运算符
// 定义优先级
#include
unordered_map pr{{'+',1}, {'*', 2}, {'-', 1}, {'/', 2}};
if(是运算符时)
{
// eval()即计算
while( op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
为什么不用while却用if呢
因为前面可能会有多个运算符等级相同的或者大于它的,要将它们全部计算完才行
比如 1 - 1 * 2 + 1
如果只计算一次就变成了1 + 2 - 1,看式子确实没错
但是栈顶的两个数可是2和1,第二次再计算就是1 - 2得到-1
原式的值是0
evaluation()
void eval()
{
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '*') x = a * b;
else if (c == '-') x = a - b;
else x = a / b;
num.push(x);
}
// 比较简单不做过多的解释
总代码
#include
#include
#include
#include
#include
#include
using namespace std;
stack num;
stack op;
unordered_map pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
void eval()
{
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char ch = op.top(); op.pop();
int x;
if (ch == '+') x = a + b;
else if (ch == '-') x = a - b;
else if (ch == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
string str;
cin >> str;
for(int i = 0; i < str.size(); i ++)
{
char c = str[i];
if(isdigit(c))
{
int x = 0, j = i;
while(j < str.size() && isdigit(str[j]))
{
x = x * 10 + str[j] - '0';
j ++;
}
i = j - 1;
num.push(x);
}
else if (c == '(') op.push(c);
else if (c == ')')
{
while(op.top() != '(') eval();
op.pop();
}
else
{
while( op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}
更加简单的
Original: https://www.cnblogs.com/hhc-blog/p/15430744.html
Author: hcのBlog
Title: 表达式求值
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/584620/
转载文章受原作者版权保护。转载请注明原作者出处!