算法题：四则运算（中缀式到后缀式的转换，值得思考的逆波兰式）

分类：算法

逆波兰式

/*字符串的四则运算。给出一个字符串，包含0~9的数字和 + -*\/ ()的运算符，- 仅代表减号不代表负数。举例如下：输入：1 + 2 * (3 – 4)*//*我的总结：计算机无法理解人类的正向思维，于是为了满足计算机的思维，，我们会反其道而行之，将操作符号放在操作数的后面，形成后缀表达式，但是如果你能按百科上说的思维来做，那么轻而易举的就可以得到答案。*//*1.根据表达式构造逆波兰表达式。2.根据逆波兰表达式进行计算。3.最终可以轻易的得到结果，我希望大家可以学习一下，共勉。*/;bool Is_Op(char ch){return (ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ || ch == ‘(‘ || 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 != ‘\0’){if (*fp == ‘(‘)flags++;if (*fp == ‘)’)flags–;fp++;}if (flags != 0)return -1;//开始构造波兰表达式。strcat(str, “#”);char *p = str;char *q = str;stack<char> OP;OP.push(‘#’);stack<string> NM;int count = 0;string s;while (*p != ‘\0’){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 == ‘\0’ || *p == ‘#’)break;}char buff[255];memset(buff, 0, sizeof(buff));itoa(count, buff, 10);s = buff;NM.push(s);count = 0;}}stack<string> numSt;while (NM.empty() == false){numSt.push(NM.top());//逆序。NM.pop();}//目前为止已经构造好了逆波兰式,下面让我们来计算吧。stack<int> 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”);<< Grial(s) << endl;return 0;}

上一篇算法题：剔除字符串（很有意思）下一篇算法题：n个括号的合法全排列

顶1踩1

纵然伤心，也不要愁眉不展，因为你不知是谁会爱上你的笑容

相关文章：

你感兴趣的文章：

标签云：