数据结构实验三 用栈实现进制转换和计算器

admin管理员组

文章数量:1794759

数据结构实验三 用栈实现进制转换和计算器

在c++中栈已经有stl容器定义过了，在这里面我就不写栈的定义的那部分了（因为太麻烦了） 进制转换非常简单，尤其是这次只要求了十以内进制的转换，我们只需要先输入要转换的进制t，然后输入要转换的数n，每次求n对进制t取模，压入栈中，最后再一直pop到栈为空即可. 代码如下

void Dataturn(int t,int n) { stack<int> s; if(n==0)cout<<0<<endl; else{ while(n){ s.push(n%t); n/=t; } while(!empty(s)){ cout<<s.top(); s.pop(); } } }

实现计算器相对来说比较麻烦，需要先进行我们常用的中缀表达式转换成计算机能线性一次读完的后缀表达式（又叫波兰式），实现转换后就非常简单了，我们在进行转换之前需要对运算符的优先级进行比较，我们可以bool一个cmp函数来进行运算符优先级的比较

bool cmp(char a,char b) { if (a == '+'&&b == '(') return true; if (a == '-'&&(b == '*'||b == '('||b == '/')) return true; if (a == '*'&&(b == '+'||b == '-'||b == '(')) return true; if (a == '/'&&(b == '+'||b == '-'||b == '(')) return true; return false; }

然后就可以写转换成后缀表达式的部分了 由于这次只要求进行十以内的数在计算器中进行运算，我们就并不需要进行数位的判断（当然加上也并不难，笔者在这里就不写了，读者们如果有需要可以自己研究一下） 我们传入一个字符串s，再定义一个字符串res，然后遍历s将其传入res和栈来转化，

string turn_back(string s) { string res; stack<char> op; int len = s.length(); for (int i = 0; i < len; i++) { if (s[i]-'0'>=0&&s[i]-'0'<=9) res += s[i]; if (s[i] == '(') op.push(s[i]); if (s[i] == '+'||s[i]=='*'||s[i]=='-'||s[i]=='/'){ if (op.empty()) op.push(s[i]); else while (1){ char temp = op.top(); if (cmp(s[i], temp)){ op.push(s[i]); break; } else{ res += temp; op.pop(); if (op.empty()) { op.push(s[i]); break; } } } } if (s[i] == ')'){ while (op.top() != '('){ res += op.top(); op.pop(); } op.pop(); } } while (!op.empty()){ res += op.top(); op.pop(); } return res; }

测试输入2+3+4+(52)-6/3 可得输出23+4+52+63/- 可见成功将中缀表达式转换成了后缀表达式 在计算器的实现中我们只需要传入这个后缀表达式，然后对s逐位进行运算，如果s[i]是数字，就将其压入栈，如果是符号，就将栈内栈顶的两个数字进行计算，然后再压入栈，如果是不满足交换律的运算符要记住将其反过来运算，因为比较简单就不贴代码了。 还有一种计算器的实现方法是直接对s进行运算，不需要转化成res，不过由于时间有限，笔者没有研究那种方法，如果有会的读者或者有相关链接的读者可以把链接在评论区发一下

本文标签： 数据结构计算器