数据结构课后的实验作业
主要模块为：
转换模块：将中缀表达式转换为后缀表达式；
运算模块：对后缀表达式进行运算，得到最终运算结果。
运行环境为Ubuntu，g++版本为9.3.0
运算范围只限在32位整形以内
运算符包括了加减乘除、取余和幂次
可以进一步扩展的有：增加实数范围的运算；扩展运算符，例如根号等；实现图形操作界面
使用了GNU的开源readline库来实现比较人性化的行编辑器功能，具体的操作在这篇博客中
源码：
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>
#include <memory>
#include <utility>
#include <readline/readline.h>
#include <readline/history.h>
#include <cmath>
using namespace std;
bool Error(false); //全局变量判断表达式是否非法
void Execute(void);
string Transform(const string&);
int weight(const char); //判断算符的权重
int calculate(const string&);
void calculate_operater(const string&, stack<int>&);
int main(void)
{
Execute();
return 0;
}
void Execute(void)
{
string Aline;
int num;
//命令行历史功能初始化
using_history();
while(true)
{
//读取一行中缀表达式
Aline = readline("enter expression, or q to quit: ");
//转化为后缀表达式
Aline = Transform(Aline);
if(Aline == "exit")
{
cout << "invalid charactor or syntax error!" << endl;
continue;
}
if(Aline == "")
{
continue;
}
//处理后缀表达式，得到最终运算结果
num = calculate(Aline);
if(Error)
{
cout << "invalid charactor or syntax error!" << endl;
Error = false;
continue;
}
cout << num << endl;
}
return;
}
string Transform(const string& line)
{
if(line == "q")
{
exit(1);
}
//将这个字符串添加到命令行历史中
add_history(line.c_str());
stack<char> Stack_charactors;
string ret;
string num;
string Aline;
bool flag(true);
if(line[0] == '-')
{
Aline += '0';
}
Aline += line + "#";
//cout << Aline << endl;
//解析字符串
for(auto itc = Aline.cbegin(),
ite = Aline.cend(); ite!=itc; ++itc)
{
//空格直接跳过
if(*itc == ' ')
{
continue;
}
//如果是数字
else if(*itc >= '0' && *itc <= '9')
{
num += *itc;
flag = true;
}
else
{
if(weight(*itc) == -1)
{
return "exit";
}
if(flag == true)
{
ret = ret + num + " ";
num = "";
}
if(Stack_charactors.empty() || (*itc == '('))
{
Stack_charactors.push(*itc);
}
else if(*itc == ')')
{
while(Stack_charactors.top() != '(')
{
ret = ret + Stack_charactors.top() + " ";
Stack_charactors.pop();
if(Stack_charactors.empty())
{
return "exit";
}
}
Stack_charactors.pop();
}
else
{
while((!Stack_charactors.empty()) && (weight(*itc) <= weight(Stack_charactors.top())))
{
ret = ret + Stack_charactors.top() + " ";
Stack_charactors.pop();
}
Stack_charactors.push(*itc);
}
flag = false;
}
}
ret.resize(ret.size()-1);
return ret;
}
int weight(const char sign)
{
switch(sign)
{
case '#':
{
return 0;
}
case '+':
{
return 1;
}
case '-':
{
return 1;
}
case '*':
{
return 2;
}
case '/':
{
return 2;
}
case '%':
{
return 2;
}
case '^':
{
return 3;
}
case '(':
{
return 0;
}
case ')':
{
return 0;
}
default:
{
return -1;
}
}
}
int calculate(const string& expression)
{
int ret;
istringstream is(expression);
string item;
stack<int> Stack_nums;
while(is >> item)
{
if((item=="+") || (item=="-") || (item=="*") || (item=="/") || (item=="%") || (item=="^"))
{
calculate_operater(item, Stack_nums);
if(Error)
{
return 0;
}
}
else
{
Stack_nums.push(atoi(item.c_str()));
}
}
return Stack_nums.top();
}
void calculate_operater(const string& sign, stack<int>& Stack_nums)
{
int t1, t2;
if(sign == "+")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(t1 + t2);
}
else if(sign == "-")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(t1 - t2);
}
else if(sign == "*")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(t1 * t2);
}
else if(sign == "/")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(t1 / t2);
}
else if(sign == "%")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(t1 % t2);
}
else if(sign == "^")
{
if(Stack_nums.size() < 2)
{
Error = true;
return;
}
t2 = Stack_nums.top();
Stack_nums.pop();
t1 = Stack_nums.top();
Stack_nums.pop();
Stack_nums.push(pow(t1, t2));
}
return;
}