表达式求值和转换
2023-11-02 00:16 由
NOTHINGBUTNOTHING 发表于
#其他
#include<iostream>
using namespace std;
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<unordered_map>
const int maxn = 100020;
stack<double>num; //数字栈
stack<char>op; //运算符栈
void eval() //用于中缀表达式计算
{
auto b = num.top(); //考虑运算顺序,先取出来的是第二个运算数
num.pop();
auto a = num.top();
num.pop();
auto c = op.top();
op.pop();
double x = 0;
if (c == '+')x = a + b;
else if (c == '-')x = a - b;
else if (c == '*')x = a * b;
else x = a / b;
num.push(x);
}
bool eval_(char c) //用于后缀表达式
{
auto b = num.top(); //考虑运算顺序,先取出来的是第二个运算数
num.pop();
auto a = num.top();
num.pop();
int x = 0;
if (c == '+')x = a + b;
else if (c == '-')x = a - b;
else if (c == '*')x = a * b;
else {
if (b == 0)
{
cout << "Error: " << a << "/0";
return false;
}
x = a / b;
}
num.push(x);
return true;
}
//中缀表达式求值函数
void evalmerge(string str)
{
unordered_map<char, int>pr{ {'+',1},{'-',1},{'*',2},{'/',2} }; //定义一个哈希表,存储优先级
for (int i = 0; i < str.size(); i++)
{
auto c = str[i];
if (isdigit(c)||c=='-'&&(i==0||str[i-1]=='('))
{
int flag = 1, xiaoshuwei = 1;
double x = c - '0', j = i + 1;
if (c == '-')
{
x = 0;
}
while (j < str.size() && (isdigit(str[j])||str[j]=='.'))
{
if (str[j] == '.')
{
flag = 0; //说明是小数了
j++;
continue;
}
if (!flag) //小数部分
{
x =x+ (1.0*(str[j] - '0'))/pow(10, xiaoshuwei);
xiaoshuwei++;
j++;
}
else
{
x = x * 10 + str[j++] - '0'; //这里的j是要自增的
}
}
i = j - 1; //别忘记了更新i
if (c == '-')
{
x = -x;
}
num.push(x);
}//取出数字
else if (c == '+' && (i == 0 || str[i - 1] == '('))
{
continue;
}
else if (c == '(') //如果是左括号,入栈即可
{
op.push(c);
}
else if (c == ')') //如果是右括号,就意味着我们应该把目前栈里面的运算符都计算完
//并且我们知道,遇到优先级比当前栈顶优先级低的运算符,我们就会先把栈顶运算符操作完
//那么,还留在栈里面的操作符都是优先级递增的,所以要从右往左算
{
while (op.top() != '(') eval(); //一直计算完整个括号
op.pop(); //弹出左括号
}
else //一般情况
{
while (op.size() && pr[op.top()] >= pr[c])//符号栈没空,并且栈顶的运算符优先级大于当前运算符
{
eval(); //操作栈顶的运算符
}
op.push(c); //新的运算符压入栈
}
}
while (op.size()) //把最后剩下的运算符操作完
{
eval();
}
cout << num.top();
}
//后缀表达式求值函数,以#结尾,每个字符用空格隔开 负数粘在一起
void evallast(string str)
{
for (int i = 0; i < str.size() - 1; i++)
{
auto c = str[i];
if (isdigit(c) || (c == '-' && i + 1 < str.size() - 1 && str[i + 1] != ' '))
{
int x = c - '0', j = i + 1;
if (c == '-')
{
x = 0;
}
while (j < str.size() - 1 && isdigit(str[j]))
{
x = x * 10 + str[j++] - '0'; //这里的j是要自增的
}
i = j - 1; //别忘记了更新i
if (c == '-')
{
x = -x;
}
num.push(x);
}//取出数字
else if (c != ' ')
{
if (num.size() < 2)
{
cout << "Expression Error: " << num.top();
return;
}
else
{
bool flag = eval_(c);
if (!flag)
{
return;
}
}
}
}
if (num.size() == 1)
cout << num.top();
else
{
if (num.size() > 1)
{
cout << "Expression Error: " << num.top();
}
}
}
//中缀转后缀
string transe(string str)
{
string ans; //存储结果表达式
stack<int>shu;
stack<char>fu;
unordered_map<char, int>pr{ {'+',1},{'-',1},{'*',2},{'/',2} }; //定义一个哈希表,存储优先级
for (int i = 0; i < str.size(); i++)
{
auto c = str[i];
if (isdigit(c) || c == '-' && (i == 0 || str[i - 1] == '('))
{
string temp;
temp += c;
int x = c - '0', j = i + 1;
while (j < str.size() && (isdigit(str[j]) || str[j] == '.'))
{
temp += str[j];
j++;
}
i = j - 1; //别忘记了更新i
ans += temp; //直接放到结果表达式中
ans += " ";
}//取出数字
else if (c == '+' && (i == 0 || str[i - 1] == '('))
{
continue;
}
else if (c == '(') //如果是左括号,入栈即可
{
fu.push(c);
}
else if (c == ')') //如果是右括号,就意味着我们应该把目前栈里面的运算符都计算完
//并且我们知道,遇到优先级比当前栈顶优先级低的运算符,我们就会先把栈顶运算符操作完
//那么,还留在栈里面的操作符都是优先级递增的,所以要从右往左算
{
while (fu.top() != '(')
{
auto tempfu = fu.top();
fu.pop();
ans += tempfu;
ans += " ";
}
fu.pop(); //弹出左括号
}
else //一般情况
{
while (fu.size() && pr[fu.top()] >= pr[c])//符号栈没空,并且栈顶的运算符优先级大于当前运算符
{
auto temp = fu.top();
fu.pop();
ans += temp;
ans += " ";
}
fu.push(c); //新的运算符压入栈
}
}
while (fu.size()) //把最后剩下的运算符操作完
{
auto temp = fu.top();
fu.pop();
ans += temp;
ans += " ";
}
ans += '#';
return ans;
}
int main()
{
string s;
cin >> s;
evalmerge(s);
cout << endl;
while (!num.empty())
{
num.pop();
}
while (!op.empty())
{
op.pop();
}
string ss = transe(s);
cout << ss << endl;
return 0;
}
热门相关:宴先生缠得要命 高人竟在我身边 都市御魔人 我真没想重生啊 我家影后超甜的