最近这段时间看操作系统的东西看的头晕脑胀的,所以先停个一晚上,写个控制台下的计算器,来练练栈的使用。
首先,分析一下要完成的东西。输入肯定使用string类来输入的,然后第一步,就是把string的字符串转化成数字存储起来。转化的这个数字存储是中序表达式,由于运算符有优先级的问题,中序表达式直接计算结果不好计算,所以需要把他转化成后序表达式,最后进行计算。
主要的函数:
(1)把string转化为中序表达式,用vector<double>的类型存储。
(2)把中序表达式转化为后序表达式。
(3)从后序表达式里面,进行计算,得到计算的结果。
程序部分:
一:先写个提示信息和表达式的输入函数,这个部分比较容易
1 void promptInfo() 2 { 3 cout << "please write a expression which is only includes the +-*/ and ()" << endl; 4 cout << "if you want to exit, please input the \"end\" or entry key " << endl; 5 } 6 7 void getExpression(string& expresion) 8 { 9 getline(cin, expresion); 10 //在表达式后面多加一个空格,有利于下面的转化中序表达式 11 expresion = expresion + " "; 12 }
这两个函数里面,在得到了输入的表达式后,人为的给表达式加了一个空格:
expresion = expresion + " ";
这个主要考虑到后面把输入的string表达式转化为中序表达式的步骤。后面会再说。其他部分没有什么,都是比较简单的输入输出。
二:string转化为中序表达式
在这个部分,要把string转化double型的数据。主要有以下几个难点:
1.表达式里面的符号的存储方法.
2.表达式中的数字有小数,要考虑到这点。
2.1 表达式符号的存储
表达式里面,如果假设表达式是正确输入的话,那里面除了数字,就全部都是符号了,总共有:+-*/() .7种类型。数字是0—9,那也就是说,在表达式里面,是不可能出现负数的(-3会被解析为一个“-”和数字3).所以初步想法就是把表达式里面的符号用负数来存储。+-*/(). 这7个符号分别对应-1—-7。为了增加可读性,用宏定义的方法来表示7中特殊的符号
#define ADD -1 #define MINUS -2 #define MUL -3 #define DIVIDE -4 #define L_BRACKET -5 #define R_BRACKET -6 #define DOT -7
2.2表达式里面的小数
表达式里面的小数,使用一个标示变量dotFlag。如果在表达式的遍历过程中,出现了.小数点这个符号,则dotFlag+1,并且对他后面的字符串遍历过程中,在遇到特殊符号或者空格之前,不断的增加dotFlag的大小,标示小数的位数,在最后把整个数字存入结果的时候,调用pow(10,dotFlag)来作为除数,得到相应的小数。也就是首先把在字符串里面出现的所有的数字当成是整数,如果出现小数点,用dotFlag来记录小数的位数,最后用得到的字符串的整数来/pow(10,dotFlag),来得到相应的小数。
2.3
整个转化函数如下:
1 vector<double> strToDouble(const string& expression) 2 { 3 vector<double> ret; 4 int dotFlag = -1; //dotFlag表示小数位数 5 double num = -1; 6 int strSize = expression.size(); 7 const char* str = expression.c_str(); 8 for (int i = 0; i<strSize; ++i) 9 { 10 int temp = table(str[i]); 11 if (temp == 10){ 12 if (num != -1){ 13 if (dotFlag == -1) //如果没有出现小数点,则需要加上1 14 dotFlag++; 15 num = num / pow(10, dotFlag); 16 ret.push_back(num); 17 } 18 19 dotFlag = -1; 20 num = -1; 21 continue; 22 } 23 if (temp >= 0 && temp<=9 ) { 24 if (num == -1) 25 num = 0; 26 num = num * 10 + temp; 27 if (dotFlag >= 0) 28 dotFlag++; 29 continue; 30 } 31 32 if (temp == DOT) { 33 dotFlag++; 34 continue; 35 } 36 37 if (num != -1) 38 { 39 if (dotFlag == -1) 40 dotFlag++; 41 num = num / pow(10, dotFlag); 42 ret.push_back(num); 43 } 44 ret.push_back(temp); 45 num = -1; 46 dotFlag = -1; 47 } 48 49 return ret; 50 }
整个转化函数的思路比较简单,从头开始遍历真个字符串,如果得到的char变量是数字,则使用下面的算式来得到数字,其中dotflag是小数点位数的标示变量,当遇到小数点时,dotflag就会由-1变为0,然后记录小数点后面的数字位数,在最后处理数字:
1 if (temp >= 0) { 2 if (num == -1) 3 num = 0; 4 num = num * 10 + temp; 5 if (dotFlag >= 0) 6 dotFlag++; 7 continue; 8 }
如果得到的是除了小数点以外的符号,则把前面得到的num经过处理,存储起来:
1 if (num != -1){ 2 if (dotFlag == -1) //如果没有出现小数点,则需要加上1 3 dotFlag++; 4 num = num / pow(10, dotFlag); 5 ret.push_back(num); 6 } 7 8 dotFlag = -1; 9 num = -1;
这里要注意num的值和dotFlag的值都用-1来初始化而不用零。主要是因为当num用0来初始化的时候,当num的值是0,程序无法判断是因为字符串里面的数字是0还是num是初始化的值,就无法决定要不要存储num的值。
而dotFlag初始化为-1,是因为当字符串遇到小数点时,dotflag需要加一,以后再遇到特殊符号之前每遇到一位数字,dotflag都会+1,仔细算一下就会发现,dotflag的值比真实的小数点的位数多了1,所以有两个办法,一个就是再最后把dotflag-1, 或者dotflag再初始化时就设为-1.
这里还需要解答上面一个问题,再最开始的时候,输入的表达式人为的加了一个空格符号在末尾:
expresion = expresion + " ";
这个主要考虑到,在进行strToDouble()函数时,我是在遇到一个特殊符号时,来判断是否需要把num存入中序表达式,而在字符串表达式的末尾,不一定会有特殊符号,如果最后一位是以数字结尾的,则最后的数字会丢失。所以要对这种情况加以讨论。如果针对这种特殊的情况进行讨论,则会显得比较麻烦,所以想到,在得到的string表达式的最后一位,人为的加上一个空格,保证不会丢失数字,这样的方法比前面的特殊针对,在加代码要方便的多,而且效果应该更好。
三:中序表达式转后序表达式
这个主要依据以下算法来进行转化:
1.如果数据是数字,则直接存入后序表达式的存储队列。
2.如果是符号:
2.1 若是* / (, 则存入栈
2.2 若是 +,-, 如果栈为空,则直接存入栈内。否则查看栈顶元素,如果栈顶元素是(,则直接存入栈;否则,比较栈顶元素和存入元素的优先级,如果栈顶元素优先级较高(如* /),则压出栈顶元素,存入后序表达式队列,继续比较新的栈顶元素,直到两者的优先级相同或者栈顶元素的优先级小于要压入的元素。
2.3如果是右括号,则查看栈顶元素,如果栈顶元素不是左括号,则压出元素,存入后序表达式,直到遇到左括号,丢弃左括号和右括号。
3.当中序表达式遍历完成,压出栈内所有元素,按照出栈顺序来存入后序表达式。
举例:2+3*(4+5)转化为后序表达式就是:2 3 4 5 + * +
代码如下:
1 vector<double> midToPost(const vector<double>& midOrder) 2 { 3 vector<double> postOrder; 4 stack<double> op; 5 int length = midOrder.size(); 6 for (int i = 0; i < length; ++i) 7 { 8 double temp = midOrder[i]; 9 // 数字直接入列 10 if (temp >= 0){ 11 postOrder.push_back(midOrder[i]); 12 continue; 13 } 14 //符号分情况讨论 15 else{ 16 //( * / 三种符号直接入列 17 if (temp == L_BRACKET || temp == MUL || temp == DIVIDE){ 18 op.push(temp); 19 continue; 20 } 21 //+ - 分情况讨论,查看栈顶符号的优先级 22 if (temp == ADD || temp == MINUS){ 23 if (op.empty() || op.top() == ADD || op.top() == MINUS || op.top() == L_BRACKET){ 24 op.push(temp); 25 continue; 26 } 27 else{ 28 int stackOp = op.top(); 29 postOrder.push_back(stackOp); 30 op.pop(); 31 i--; //反复查询 32 continue; 33 } 34 } 35 36 if (temp == R_BRACKET){ 37 int stackOp = op.top(); 38 op.pop(); 39 if (stackOp != L_BRACKET){ 40 postOrder.push_back(stackOp); 41 i--; //反复查询 42 } 43 44 } 45 46 } 47 } 48 while (!op.empty()){ 49 postOrder.push_back(op.top()); 50 op.pop(); 51 } 52 return postOrder; 53 } 54
四:通过后序表达式计算结果
有了后序表达式,来计算结果就比较简单了,过程就是遍历后序表达式,如果是数字,则压入栈内,如果是符号,则把连续压出栈内的两个数字,按顺序进行相关的计算,然后把结果压入栈内。最后栈内的数字就是计算的结果
代码如下:
double calculate(const vector<double>& postOrder) { stack<double> num; auto length = postOrder.size(); for (int i = 0; i < length; i++){ double temp = postOrder[i]; if (temp >= 0){ num.push(temp); continue; } else{ double postNum = num.top(); num.pop(); double preNum = num.top(); num.pop(); double result; switch ((int)temp){ case ADD: result = preNum + postNum; break; case MINUS: result = preNum - postNum; break; case MUL: result = preNum * postNum; break; case DIVIDE: result = preNum / postNum; break; } num.push(result); continue; } } return num.top(); }
总结:
这个计算器的程序,感觉最麻烦的部分还是在字符串转化为中序表达式,其他的两个部分就是栈的一个简单的应用,中序表达式转为后序表达式只要知道相关的算法,还是蛮容易的。后面的后序表达式计算结果,也比较简单。
这个控制台的计算器,还是很简陋的,最大的问题,就是要求输入的算是必须是正确的,比如,你不能输((3+5)这样的算式,在程序里面,无法检测出来,这是一个最大的问题。如果要改,还需要加入相应的代码,但其实都差不多,这里就不在加了。
后期如果相加上其他更多的操作其实也行,比如加上2^3这样的操作符,只要在相应的代码部分添加就可以。
最后,本来编写这个程序实在Ubuntu的sublime text 3下编的。可能自己太low,总感觉很不舒服,最后还是回到windows下用VS编了,到现在为止,还是感觉vs用起来最爽。
附上完整程序的代码:
#include<iostream> #include<string> #include<cmath> #include<stack> #include<vector> using namespace std; #define ADD -1 #define MINUS -2 #define MUL -3 #define DIVIDE -4 #define L_BRACKET -5 #define R_BRACKET -6 #define DOT -7 void promptInfo();//提示信息 void getExpression(string& expresion);//得到表达式 vector<double> strToDouble(const string& expression);//字符串表达式转化为数字型的中序表达式 int table(char c); vector<double> midToPost(const vector<double>& midOrder);//中序表达式转化为后序表达式 double calculate(const vector<double>& postOrder);//通过后序表达式得到计算结果 int main() { while (1) { string expression; promptInfo(); getExpression(expression); if (expression == "end " || expression == " ") break; vector<double> midOrder = strToDouble(expression); vector<double> postOrder = midToPost(midOrder); double result = calculate(postOrder); cout << expression << "= " << result << endl; } return 0; } void promptInfo() { cout << "please write a expression which is only includes the +-*/ and ()" << endl; cout << "if you want to exit, please input the \"end\" or entry key " << endl; } void getExpression(string& expresion) { getline(cin, expresion); //getline不会输入最后的换行符,所以加一个字符进去,防止最后一个数字被忽略 expresion = expresion + " "; } vector<double> strToDouble(const string& expression) { vector<double> ret; int dotFlag = -1; //dotFlag表示小数位数 double num = -1; int strSize = expression.size(); const char* str = expression.c_str(); for (int i = 0; i<strSize; ++i) { int temp = table(str[i]); if (temp == 10){ if (num != -1){ if (dotFlag == -1) //如果没有出现小数点,则需要加上1 dotFlag++; num = num / pow(10, dotFlag); ret.push_back(num); } dotFlag = -1; num = -1; continue; } if (temp >= 0 && temp<=9 ) { if (num == -1) num = 0; num = num * 10 + temp; if (dotFlag >= 0) dotFlag++; continue; } if (temp == DOT) { dotFlag++; continue; } if (num != -1) { if (dotFlag == -1) dotFlag++; num = num / pow(10, dotFlag); ret.push_back(num); } ret.push_back(temp); num = -1; dotFlag = -1; } return ret; } int table(char c) { switch(c){ case '0': return 0; break; case '1': return 1; break; case '2': return 2; break; case '3': return 3; break; case '4': return 4; break; case '5': return 5; break; case '6': return 6; break; case '7': return 7; break; case '8': return 8; break; case '9': return 9; break; case '+': return ADD; break; case '-': return MINUS; break; case '*': return MUL; break; case '/': return DIVIDE; break; case '(': return L_BRACKET; break; case ')': return R_BRACKET; break; case '.': return DOT; break; default: return 10; //其他情况或者空格 } } vector<double> midToPost(const vector<double>& midOrder) { vector<double> postOrder; stack<double> op; int length = midOrder.size(); for (int i = 0; i < length; ++i) { double temp = midOrder[i]; // 数字直接入列 if (temp >= 0){ postOrder.push_back(midOrder[i]); continue; } //符号分情况讨论 else{ //( * / 三种符号直接入列 if (temp == L_BRACKET || temp == MUL || temp == DIVIDE){ op.push(temp); continue; } //+ - 分情况讨论,查看栈顶符号的优先级 if (temp == ADD || temp == MINUS){ if (op.empty() || op.top() == ADD || op.top() == MINUS || op.top() == L_BRACKET){ op.push(temp); continue; } else{ int stackOp = op.top(); postOrder.push_back(stackOp); op.pop(); i--; //反复查询 continue; } } if (temp == R_BRACKET){ int stackOp = op.top(); op.pop(); if (stackOp != L_BRACKET){ postOrder.push_back(stackOp); i--; //反复查询 } } } } while (!op.empty()){ postOrder.push_back(op.top()); op.pop(); } return postOrder; } double calculate(const vector<double>& postOrder) { stack<double> num; auto length = postOrder.size(); for (int i = 0; i < length; i++){ double temp = postOrder[i]; if (temp >= 0){ num.push(temp); continue; } else{ double postNum = num.top(); num.pop(); double preNum = num.top(); num.pop(); double result; switch ((int)temp){ case ADD: result = preNum + postNum; break; case MINUS: result = preNum - postNum; break; case MUL: result = preNum * postNum; break; case DIVIDE: result = preNum / postNum; break; } num.push(result); continue; } } return num.top(); }
版权声明:本文为博主原创文章,未经博主允许不得转载。