问题分析
- 上一节我们已经知道该如何将中缀表达式转为后缀表达式（传送门），这里我们将直接将实际计算一个表达式，比如
#，要求表达式结尾以’#‘结束；
实现方法
得到后缀表达式
- 这里我们用==队列==存储后缀表达式结果；
- 另一方面值得注意的是这里的操作数是不知几位的数字，在转后缀的要值得注意（
小树我自己踩过的坑 ），解决方法是在遇到操作符前将操作数的每一位存储在一个字符串中，在遇到操作符时，将其存储在队列中，然后将字符串清空，存储下个操作数。具体代码如下：
//判断是否为运算符
bool is_operator(const char temp)
{
return temp == '+' || temp == '-' || temp == '/' || temp == '*' || temp == '(' || temp == ')';
}
//得到运算符优先级
long long level_operator(char temp)
{
if (temp == '+' || temp == '-')return 2;
else if (temp == '*' || temp == '/')return 1;
else return 0;
}
//中缀转后缀
queue<string>* Infix_convert(string ex)
{
if (ex.back() != '#')ex.append(1, '#');
//得到表达式长度
stack<char>op;
op.push('#');
//将后缀结果存储在队列中
queue<string>*re=new queue<string>;
//记录数字
string infix_ex;
for (int i = 0; ex[i] != '#'; i++)
{
if (!is_operator(ex[i]))infix_ex.append(1,ex[i]);//将操作数的每一位存储
else if (ex[i] == ')')
{
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
for (; op.top() != '('; op.pop())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
}
op.pop();
}
else
{
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
for (; level_operator(op.top()) <= level_operator(ex[i]) && op.top() != '#' && op.top() != '('; op.pop())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
}
op.push(ex[i]);
}
}
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
while (!op.empty())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
op.pop();
}
return re;
}
操作数字符串转为数字
//将字符串转为数字
long long string_to_int(string temp)
{
int length = temp.size();
long long re = 0;
for (int i = 0; i < length; i++)
{
long long pi = 1;
for (int j = length - i - 2; j >= 0; j--)
{
pi *= 10;
}
re += (long long(char(temp[i])) - 48)*pi;
}
return re;
}
计算过程
-
在后缀表达式队列中从队首读取，操作数存储在栈中，当在队列中读取到操作符时，将栈的栈顶前两位取出计算，并将结果存储在栈中，以此往复，代码如下：
//一般计算
long long Basic_eval(long long a, long long b, string op)
{
if (op == "+")return a + b;
else if (op == "-")return a - b;
else if (op == "*")return a * b;
else if (op == "/")return a / b;
else throw"Cann't Eval!";
}
//计算表达式
long long Eval(string ex)
{
//转为后缀表达式
queue<string>*ex_inf;
ex_inf = Infix_convert(ex);
//储存计算结果
stack<long long>data;
for (; ex_inf->front() != "#"; ex_inf->pop())
{
if (!is_operator_s(ex_inf->front()))data.push(string_to_int(ex_inf->front()));
else
{
long long dataB = data.top();
data.pop();
long long dataA = data.top();
data.pop();
data.push(Basic_eval(dataA, dataB, ex_inf->front()));
}
}
return data.top();
}
代码总览
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
//判断是否为运算符
bool is_operator(const char temp)
{
return temp == '+' || temp == '-' || temp == '/' || temp == '*' || temp == '(' || temp == ')';
}
//判断是否为运算符
bool is_operator_s(const string temp)
{
return temp == "+" || temp == "-" || temp == "/" || temp == "*" || temp == "(" || temp == ")";
}
//得到运算符优先级
long long level_operator(char temp)
{
if (temp == '+' || temp == '-')return 2;
else if (temp == '*' || temp == '/')return 1;
else return 0;
}
//中缀转后缀
queue<string>* Infix_convert(string ex)
{
if (ex.back() != '#')ex.append(1, '#');
//得到表达式长度
stack<char>op;
op.push('#');
//将后缀结果存储在队列中
queue<string>*re=new queue<string>;
//记录数字
string infix_ex;
for (int i = 0; ex[i] != '#'; i++)
{
if (!is_operator(ex[i]))infix_ex.append(1,ex[i]);
else if (ex[i] == ')')
{
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
for (; op.top() != '('; op.pop())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
}
op.pop();
}
else
{
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
for (; level_operator(op.top()) <= level_operator(ex[i]) && op.top() != '#' && op.top() != '('; op.pop())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
}
op.push(ex[i]);
}
}
//将数字字符串储存在队列中
if (!infix_ex.empty())
{
re->push(infix_ex);
infix_ex.clear();
}
while (!op.empty())
{
//将字符转为字符串
char temp[2] = { op.top(),0 };
re->push(temp);
op.pop();
}
return re;
}
//将字符串转为数字
long long string_to_int(string temp)
{
int length = temp.size();
long long re = 0;
for (int i = 0; i < length; i++)
{
long long pi = 1;
for (int j = length - i - 2; j >= 0; j--)
{
pi *= 10;
}
re += (long long(char(temp[i])) - 48)*pi;
}
return re;
}
//一般计算
long long Basic_eval(long long a, long long b, string op)
{
if (op == "+")return a + b;
else if (op == "-")return a - b;
else if (op == "*")return a * b;
else if (op == "/")return a / b;
else throw"Cann't Eval!";
}
//计算表达式
long long Eval(string ex)
{
//转为后缀表达式
queue<string>*ex_inf;
ex_inf = Infix_convert(ex);
//储存计算结果
stack<long long>data;
for (; ex_inf->front() != "#"; ex_inf->pop())
{
if (!is_operator_s(ex_inf->front()))data.push(string_to_int(ex_inf->front()));
else
{
long long dataB = data.top();
data.pop();
long long dataA = data.top();
data.pop();
data.push(Basic_eval(dataA, dataB, ex_inf->front()));
}
}
return data.top();
}
//主函数
int main()
{
string ex;
cout << "请输入表达式：" << endl;
cin >> ex;
cout <<"=\t"<< Eval(ex) << endl;
return 0;
}
上一节：数据结构-栈与队列--中缀转后缀表达式
