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)
评论前必须登录!
注册