PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C++语言基础(18-1)_栈的应用中缀表达式计算

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)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C++语言基础(18-1)_栈的应用中缀表达式计算

分享到:更多 ()

评论 76

评论前必须登录!