当前位置:首页 > 公司荣誉 >

算法题:四则运算(中缀式到后缀式的转换,值得思考的

算法题:四则运算(中缀式到后缀式的转换,值得思考的逆波兰式) /* 字符串的四则运算。给出一个字符串, 包含0~9的数字和 + -*/ ()的运算符, - 仅代表减号不代表负数。举例如下: 输入:1 + 2 * (3 - 4) */ //哈哈,看到这道题,其实一点也不难,这个题根本就不用思考, //当然是你明白算法之后,这里要用到的算法是逆波兰式。 //如果你有不明白的地方,可以上网搜逆波兰式。 /* 我的总结:计算机无法理解人类的正向思维,于是为了满足计算机的 思维,我们会反其道而行之,将操作符号放在操作数的后面,形成后缀 表达式,但是如果你能按百科上说的思维来做,那么轻而易举的就可以 得到答案。 */ /* 1.根据表达式构造逆波兰表达式。 2.根据逆波兰表达式进行计算。 3.最终可以轻易的得到结果,我希望大家可以学习一下,共勉。 */ //Start: #include #include #include using namespace std; bool Is_Op(char ch) ch == '#'); bool Is_Com(char ch1, char ch2) { //比较符号表达是的优先级。 int i = 0; int j = 0; for (; #+-*/()[i] != ch1; i++){} for (; #+-*/()[j] != ch2; j++){} bool str[][7] = 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1; return str[i][j]; } int Grial(char *&str) { //先检测括号匹配是否正常吧。 int flags = 0; char *fp = str; while (*fp != '') if (*fp == '(')flags++; if (*fp == ')')flags--; fp++; if (flags != 0)return -1; //开始构造波兰表达式。 strcat(str, #); char *p = str; char *q = str; stack OP; OP.push('#'); stack NM; int count = 0; string s; while (*p != '') { if (Is_Op(*p)) { if (*p == ')') { while (OP.top() != '(') s = OP.top(); NM.push(s); OP.pop(); if (OP.top() == '(') OP.pop(); p++; continue; } if (Is_Com(OP.top(), *p) && OP.top() != '(') { while (Is_Com(OP.top(), *p)) s = OP.top(); NM.push(s); OP.pop(); if (*p == '#' && OP.top() == '#')break; OP.push(*p); } else OP.push(*p); p++; } else { while (!Is_Op(*p)) count = count * 10 + *p - '0'; p++; if (*p == '' char buff[255]; memset(buff, 0, sizeof(buff)); itoa(count, buff, 10); s = buff; NM.push(s); count = 0; } } stack numSt; while (NM.empty() == false) numSt.push(NM.top());//逆序。 NM.pop(); //目前为止已经构造好了逆波兰式,下面让我们来计算吧。 stack temp; while (numSt.empty() == false) { if (numSt.top() == + || numSt.top() == - || numSt.top() == * || numSt.top() == /) { int a = temp.top(); temp.pop(); int b = temp.top(); temp.pop(); if (numSt.top() == +) temp.push(b + a); else if (numSt.top() == -) temp.push(b - a); else if (numSt.top() == *) temp.push(b*a); else if (numSt.top() == /) temp.push(b / a); numSt.pop(); } else temp.push(atoi(numSt.top().c_str())); numSt.pop(); } return temp.top(); } int main() ; char *s = new char[20]; memset(s, 0, sizeof(s)); strcpy(s, (1+2)*3-(1+2)/4+10); cout << Grial(s) << endl; strcpy(s, 1+2+4+(1*2)/3+4); cout << Grial(s) << endl; strcpy(s, 3+(4/2)+1+2-1*2); cout << Grial(s) << endl; strcpy(s, (1+(2+3)*4)+2-0); //我还担心自己的双重括号没有考虑到, //没想到一次成功。 cout << Grial(s) << endl; return 0;

这里写图片描述

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站推广 https://www.feimao666.com

上一篇:php生成rss订阅

下一篇:最后一页