PPC的C/C++和人工智能学习笔记C++基础语法基本学完了，今天做个练习，使用一下栈。
练习内容：给出一个字符串表达式(有+-*/和括号)，计算其结果，比如：（2+3.0*1.5)*2-5*(2-1)，判断其正确性（比如有出现其他非空格字符，出现除0错误），正确输出结果（2位小数的浮点数），错误输出错误原因，最后可以接受输入文件（字符串以文件的形式提供），结果输出到文件中。
先学习几个概念和算法：
后缀表达式及求值：
后缀表达式也称为逆波兰表达式，可以用栈辅助其求值。比如我们有表达式：
1+2*3-4，其后缀表达式为123*+4- （具体怎么转换的后面讲），计算结果是3。
执行流程：遍历后缀表达式，遇到数字压栈，遇到运算符出栈2个数字并用该操作符计算结果后入栈，直到遍历完成。
中缀表达式转后缀表达式：
我们通过上面的后缀表达式发现，后缀表达式没有括号，运算起来很简单方便，而我们平时的写法都是中缀表达式（如上面的1+2*3-4），所以需要转换，中缀表达式转换到后缀表达式的规则：
优先级定义：() 最高，乘除同级次之，加减同级最后。
我们用2块来存储数据，一个是栈（临时用），一个是输出结果（最终结果）。在遍历表达式的过程中：
1）遇到数字直接到输出结果；
2）遇到非括号运算符，依次将栈中优先级别>=该运算符的运算符弹出到输出结果（如果栈顶的运算符优先级<该运算符，则不弹出任何运算符），弹出后再将该运算符入栈。注意：遇到括号不弹出。
3）遇到左括号，入栈；
4）遇到右括号，出栈运算符到输出结果，直到遇到栈中的左括号。注意：左括号只出栈不写到输出结果。
5）表达式扫描结束，依次弹出栈中运算符到输出结果。
另一种转换方法:
1）先按照运算符的优先级对中缀表达式加括号，变成( ( 1+(2*3) )-4 )
2）然后将运算符移到括号的后面，变成( ( 1(23)* )+4 )-
3）最后去掉括号，得到123*+4-
这里没有讲到前缀表达式，中缀表达式也可以转为前缀表达式，而前缀和后缀表达式计算机计算结果很容易，人则理解中缀表达式最方便，所以我们写程序进行转换。
CInfixExp类头文件：InfixExp.h
//InfixExp.h
//计算中缀表达式的值 CInfixExp类头文件
#pragma once
#ifndef _INFIXEXP_H
#define _INFIXEXP_H
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <map>
using std::cout;
using std::endl;
using std::string;
using std::stack;
using std::vector;
using std::map;
struct infixOut { //中缀转后缀的输出 结构，isval=true 表示是val值，否则是op值
union data {
double val;
char op;
}value;
bool isval;
};
class CInfixExp
{
private:
string m_input; //中缀表达式（原始表达式）
string m_infix; //去掉空格后的表达式
stack<char> m_opStack; //运算符和括号 栈（中缀转后缀用栈）
vector<infixOut> m_infixOut; //中缀转后缀的输出（最终结果就是后缀表达式）
stack<double> m_suffixStack; //后缀 计算用栈
double m_res; //计算结果
string m_error; //错误
map<char, int> m_op; //运算符优先级
public:
CInfixExp();
~CInfixExp();
void init(string& input=(string)""); //初始化
void trim(string& str); //去除所有空格
void infix2suffix(string& infix); //中缀转后缀
bool isValue(char c); //判断字符是否数字 还是 操作符
void pushInfixOut(string& str,char c,bool isVal); //到 输出
void pushpopOp(char c); //中缀转后缀 碰到操作符时的 出栈入栈操作
double suffixCal(); //后缀计算值
double calc(double d1, double d2, char c); //计算
void overcalc(); //总计算 从输入到输出,存放在 类的成员变量中
const string& getinput() const { return m_input; } //获取输入
double getres() const { return m_res; } //获取结果
const string& geterror() const { return m_error; }//获取错误
};
#endif // !_INFIXEXP_H
CInfixExp类cpp文件：InfixExp.cpp
//InfixExp.cpp
//计算中缀表达式的值 CInfixExp类cpp文件
#include "InfixExp.h"
CInfixExp::CInfixExp()
{
m_op['+'] = 0;
m_op['-'] = 0;
m_op['*'] = 1;
m_op['/'] = 1;
m_op['('] = 2;
m_op[')'] = 2;
init();
}
CInfixExp::~CInfixExp()
{
}
void CInfixExp::init(string& input) { //初始化
m_input = input;
while (!m_opStack.empty())
m_opStack.pop();
m_infixOut.clear();
while (!m_suffixStack.empty())
m_suffixStack.pop();
m_res = 0.0;
m_error = "";
}
void CInfixExp::trim(string& str) { //去除所有空格
if (str.empty()) return;
int index = 0;
while ((index = str.find(' ', index)) != string::npos) {
str.erase(index, 1);
}
}
void CInfixExp::infix2suffix(string& infix) { //中缀转后缀
m_infixOut.clear();
string tmp; //存放读出的每个数字或运算符
bool isDigit = true,isDigitOld=true; //是数字(包括.) 还是 操作符(+-*/())
string::iterator itinfix = infix.begin();
infixOut tmpInfixOut; //临时输出
while (itinfix != infix.end()) {
isDigitOld = isDigit;
isDigit = isValue(*itinfix);
if (isDigit != isDigitOld && isDigitOld) { //出现变化了，并且转到 操作符了
pushInfixOut(tmp, '0', true);
//当前是操作符
pushpopOp(*itinfix);
tmp.clear();
isDigit = isDigitOld = false;
}
else {//没出现变化，
if(isDigit) //当前还是数字
tmp += *itinfix; //添加到tmp中
else { //当前是操作符
pushpopOp(*itinfix);
}
}
if ((itinfix+1) == infix.end()) {
//最后1个输入的处理(注意最后结束不是 数字和 )的情况)
if (isDigit) { //最后是数字
pushInfixOut(tmp, '0', true);
}
//把栈中的全部弹出
while (!m_opStack.empty()) {
pushInfixOut(tmp, m_opStack.top(), false);
m_opStack.pop();
}
}
++itinfix;
}
}
void CInfixExp::pushpopOp(char c) { //中缀转后缀 碰到操作符时的 出栈入栈操作
if (m_opStack.empty()) { //空栈
m_opStack.push(c);
return;
}
string ss;
if (c != ')') {
while (!m_opStack.empty() && m_op[m_opStack.top()] >= m_op
&& m_opStack.top()!='(') {
pushInfixOut(ss, m_opStack.top(), false);
m_opStack.pop();
}
m_opStack.push(c);
}
else { //是 ')' 弹出到 '('为止,没有就抛异常
bool isFind = false;
while (!m_opStack.empty() && m_opStack.top() != '(') {
pushInfixOut(ss, m_opStack.top(), false);
m_opStack.pop();
}
if (!m_opStack.empty() && m_opStack.top() == '(') {
isFind = true;
m_opStack.pop();
}
if (!isFind) {
m_error = "括号不匹配";
throw(m_error.c_str());
}
}
}
void CInfixExp::pushInfixOut(string& str,char c,bool isVal) { //到 输出
infixOut tmpInfixOut; //临时输出
if (isVal) { //是数字
if (str.size() == 0) //tmp中存的是数字（没有可能是第1次）
return;
tmpInfixOut.isval = true;
sscanf_s(str.c_str(), "%lf", &tmpInfixOut.value.val);
//cout << "数字：" << tmpInfixOut.value.val << endl;
}
else {//是操作符
tmpInfixOut.isval = false;
tmpInfixOut.value.op = c;
//cout << "操作符：" << tmpInfixOut.value.op << endl;
}
m_infixOut.push_back(tmpInfixOut); //到 输出
}
bool CInfixExp::isValue(char c) { //判断字符是否数字 还是 操作符
if ((c >= '0' && c <= '9') || c == '.')
return true;
else if (c == '+' || c == '-' || c == '*' || c == '/' || c=='(' || c==')')
return false;
else
{
m_error = "出现其他字符";
throw(m_error.c_str());
}
}
double CInfixExp::suffixCal() { //后缀计算值
double d1, d2; //操作数
vector<infixOut>::iterator it = m_infixOut.begin();
while (it != m_infixOut.end()) {
if (it->isval)
m_suffixStack.push(it->value.val);
else { //操作符
if (!m_suffixStack.empty()) {
d2 = m_suffixStack.top();
m_suffixStack.pop();
}
else {
m_error = "运算符多了";
throw(m_error.c_str());
}
if (!m_suffixStack.empty()) {
d1 = m_suffixStack.top();
m_suffixStack.pop();
}
else {
m_error = "运算符多了";
throw(m_error.c_str());
}
m_suffixStack.push(calc(d1, d2, it->value.op));
}
++it;
}
if (m_suffixStack.size() == 1) {
double res = m_suffixStack.top();
m_suffixStack.pop();
m_res = res;
return res;
}
else {
m_error = "未知错误";
throw(m_error.c_str());
}
}
double CInfixExp::calc(double d1, double d2, char c) { //计算
switch (c) {
case '+':
return d1 + d2;
case '-':
return d1 - d2;
case '*':
return d1*d2;
case '/':
if (d2 == 0.0) {
m_error = "除数为零";
throw(m_error.c_str());
}
else {
return d1 / d2;
}
}
}
void CInfixExp::overcalc() { //总计算 从输入到输出,存放在 类的成员变量中
m_infix = m_input;
try {
trim(m_infix); //去空格
if (m_infix[0] == '+' || m_infix[0] == '-')
m_infix = '0' + m_infix;
infix2suffix(m_infix); //中缀转后缀
suffixCal(); //后缀计算值
}
catch (const char* t) {
//cout <<"错误：" << t << endl;
return;
}
}
测试文件，main.cpp
//中缀表达式测试
#include <iostream>
#include <string>
#include "InfixExp.h"
#include <fstream>
#include <assert.h>
#include <sstream>
using std::cout;
using std::endl;
using std::string;
using std::fstream;
using std::ostringstream;
int main() {
//CInfixExp类的调用方法：
CInfixExp v; //创建对象
string str = "1+2*3-4";
v.init(str); //初始化，并把需要计算的 表达式传入
v.overcalc(); //计算结果
if (v.geterror() == "") //判断是否正确
cout << "正确结果：" << v.getres() <<" 表达式：" <<v.getinput()<<endl;
else
cout << "错误：" << v.geterror() << " 表达式：" << v.getinput() << endl;
//////////////////////////////////
cout << "==============" << endl;
cout << "文件操作：" << endl;
cout << "==============" << endl;
fstream f1,f2;
string savestr;
f1.open("1.txt", std::ios::in); //文本文件打开
f2.open("2.txt", std::ios::out); //写文件
assert(f1.is_open() && f2.is_open());
while (!f1.eof()) {
//f1 >> str; //这样的输入 遇到空格断开了
std::getline(f1, str);
v.init(str); //初始化，并把需要计算的 表达式传入
v.overcalc(); //计算结果
savestr.clear();
if (v.geterror() == "") { //正确表达式
//ostringstream os;
//os << v.getres();
//savestr = os.str();
char buf[100];
sprintf_s(buf,100, "%.2lf", v.getres());
savestr = buf;
}
else
savestr = "错误:"+v.geterror();
savestr = savestr + " 表达式：";
savestr = savestr + v.getinput();
f2 << savestr << endl;
cout << savestr << endl;
}
f1.close();
f2.close();
return 0;
}
(2017-04-21 www.vsppc.com)
评论前必须登录！
注册