利用算符优先关系,实现对算术四则混合运算表达式的求值
算术表达式有三种类型:前缀,中缀,后缀表达式,而这里主要利用的是中缀和后缀表达式
我们平常使用的是中缀表达式,而后缀表达式运算的优先已经好了,所以我们用后缀表达式进行四则计算
因为后缀表达式已经达到去括号,决定运算符优先级的效果了,所以可以直接计算
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<stack>
#include <stdlib.h>
using namespace std;
string TransExpToPostexp(string& exp)
{
stack<char> optr;
string postexp;
for (int i = 0; i < exp.size(); i++)
{
if ((exp[i] >= '0' && exp[i] <= '9') || exp[i] == '.')//是数字直接进字符串
{
postexp += exp[i];
while ((exp[i+1] >= '0' && exp[i+1] <= '9') || exp[i+1] == '.')
postexp += exp[++i];
postexp += ' ';//分隔
}
else
{
if (exp[i] == '(')//是左括号进栈
optr.push(exp[i]);
else if (exp[i] == ')')//遇到右括号则出栈到左括号出栈
{
while (!optr.empty())
{
if (optr.top() == '(')//遇到左括号则出栈并退出
{
optr.pop();
break;
}
else//遇到其他操作符则添加到后缀表达式中并出栈
{
postexp += optr.top();
postexp += ' ';//分隔
optr.pop();
}
}
}
else if (exp[i] == '*' || exp[i] == '/')
{
optr.push(exp[i]);
}
else if (exp[i] == '-' || exp[i] == '+')
{
while (!optr.empty()&&optr.top()!='(')//小于等于栈顶操作符数据,则出栈*
{
postexp += optr.top();
postexp += ' ';//分隔
optr.pop();
}
//进栈
optr.push(exp[i]);
}
else//表达式错误
{
perror("exp error!");
exit(1);
}
}
}
//遍历结束,剩余操作符出栈
while (!optr.empty())
{
postexp += optr.top();
postexp += ' ';//分隔
optr.pop();
}
return postexp;
}
double Calculate(string postexp)
{
stack<double> data;//数据栈
for (int i = 0; i < postexp.size(); i++)
{
if (postexp[i] >= '0' && postexp[i] <= '9')//是数字则入栈
{
int left = i, right = i;
while (postexp[right] != ' ')
right++;
double num = atof(postexp.substr(left,right).c_str());//字符串转浮点
//cout << num << endl;
data.push(num);
i = right;
}
else//遇到操作符
{
//取栈顶两数据,注意先后顺序,后一个才是左操作数
double right = data.top();
data.pop();
double left = data.top();
data.pop();
//判断操作符,得到数据再入栈
char optr = postexp[i];
switch (optr)
{
case '+':
data.push(left + right);
break;
case '-':
data.push(left - right);
break;
case '*':
data.push(left * right);
break;
case '/':
data.push(left / right);
break;
default:
perror("optr error");
break;
}
cout << data.top() << endl;
i++;
}
}
return data.top();
}
int main()
{
string str;
while (cin >> str)
{
string postexp=TransExpToPostexp(str) ;
cout << postexp << endl;
cout << Calculate(postexp) << endl;
}
return 0;
}
参考文章:四则运算求值