表达式求值
作者:
fanbo
,
2021-11-06 19:44:18
,
所有人可见
,
阅读 251
#include<bits/stdc++.h>
#include<stack>
#include<unordered_map>
#include<string>
using namespace std;
//定义两个栈,一个操作符栈,一个运算数操作栈
stack<double>nums;
stack<char>op;
void eval()
{
//求值,这里是数据位
double a=nums.top();//取栈顶,a先进在运算符的右边,因为后进先出
nums.pop();//弹出栈顶
double b=nums.top();
nums.pop();
char p=op.top();
op.pop();
double r;//运算结果
if(p=='+') r=b+a;
if(p=='-') r=b-a;
if(p=='*') r=b*a;
if(p=='/') r=b/a;
nums.push(r);//计算结果入栈
}
//用unordered_map进行赋值,可以比较运算优先级
//key,value
unordered_map<char,int> h { {'+',1},{'-',1},{'*',2},{'/',2}};
int main()
{
string s;//表达式以字符串的形式表示
cin>>s;
//对字符串进行遍历,时间复杂度为o(N)
//用string类,可以用迭代器方法遍历,也可以用数组的普通遍历方法
for(int i=0;i<s.size();i++)
{
//如果当前字符是数字,进行压栈操作
if(s[i]-'0'<=9&&s[i]-'0'>=0)
//if(isdigit(s[i]) isdigit用来判断字符串中是否是数字,bool类型
{
//举个最简单的例子12-10,应该是把12入栈,但是这里只能一个一个字符的检测
//因此可以采用双指针的算法,从目前的点开始遍历,直到不是数字
int x=0, j=i;//x用来储存数字部分,j表示指针
while(j<s.size()&&(s[j]-'0'<=9&&s[j]-'0'>=0))
{
x=x*10+s[j]-'0';
j++;
}
nums.push(x);
i=j-1;//因为i要跳到数字最后一个位置,又j移动到了符号位,所以要减1
}
//如果是操作符
else
{
while(op.size()&&h[op.top()]>=h[s[i]])//如果栈不空,且栈内符号优先级大于当前符号,先进行运算
eval();
op.push(s[i]);//读入操作符
}
}
//读到最后数字,还没有计算完,还要进行计算
while(op.size()) eval();
cout<<nums.top()<<endl;
return 0;
}