C++代码实现逆波兰表达式 C++代码实现逆波兰表达式

本文实例为大家分享了C++实现逆波兰表达式的具体代码，供大家参考，具体内容如下
当我们输入一个数学表达式，是中缀表达式，我们首先转换为后缀表达式（逆波兰表达式），然后再进行求值。
在《大话数据结构》的104-100页有详细的介绍，下面是我理解之后的代码实现。
代码思路：
（1）首先对输入的中缀表达式合法性进行判断，bool isStringLegal(const char* str); 函数实现。
（2）然后把中缀表达式转换为后缀表达式。
（3）根据后缀表达式求出结果，double getTheResult(vector &vec); 函数实现。
注意：表达式的运算符可以输入加、减、乘、除、括号，输入的数据为整形数据，计算结果为double型数据。

#include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_STRING_LENGTH 100 /* 解析当前的整形数据，并把整形数据转换为string型 */string analyData(const char* str, int &i); /* 根据逆波兰表达式求表达式的值 */double getTheResult(vector &vec); /* 判断该字符是否是 + - * / ( ) */bool isCalChar(const char ch); /* 判断输入的中缀表达式是否合法 */bool isStringLegal(const char* str); /* 解析当前的整形数据，并把整形数据转换为string型 */string analyData(const char* str, int &i){int temp = i++; while(str[i] >= '0' && str[i] <= '9' && str[i] != '\0'){i++; } string s(str+temp,str+i); return s; } /* 根据逆波兰表达式求表达式的值 */double getTheResult(vector &vec){vector::iterator it; stack sta; string strTemp; double d = 0, d1 = 0, d2 = 0; for(it = vec.begin(); it != vec.end(); it++){strTemp = (*it); if(strTemp == "+"){d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d1 + d2; sta.push(d); }else if(strTemp == "-"){d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 - d1; sta.push(d); }else if(strTemp == "*"){d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 * d1; sta.push(d); }else if(strTemp == "/"){d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 / d1; sta.push(d); }else{const char *p = strTemp.c_str(); d = atoi(p); sta.push(d); }}return sta.top(); } /* 判断该字符是否是 + - * / ( ) */bool isCalChar(const char ch){if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')'){return true; } return false; }/* 判断输入的中缀表达式是否合法 */bool isStringLegal(const char* str){/* 判断是否是空串 */if(NULL == str){return false; } int len = strlen(str); int i = 0; int flag = 0; /* 字符串的开头和末尾是否是数字 */if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0'){return false; } for(i = 0; str[i] != '\0'; i++){/* 是否有除了加减乘除括号之外的字符 */if(isCalChar(str[i]) == false){return false; } /* 判断是否有两个连续的符号 */if(i < len-1 && isCalChar(str[i]) == true){if(isCalChar(str[i+1]) == true){return false; } } /* 判断括号是否成对 */if(str[i] == '('){flag++; }else if(str[i] == ')'){flag--; } /* 判断是否出现 )( 这样的情况 */if(flag < 0){return false; }} /* 判断括号是否匹配 */if(flag != 0){return false; } return true; } int main(void){char str[MAX_STRING_LENGTH] = {0}; int i = 0; string data; /* 存放运算符表达式的栈 */stack oper_char; /* 存放后缀表达式 */vector post_str; /* 输入中缀的表达式 */gets(str); /* 判断输入的中缀表达式是否合法 */if(isStringLegal(str) != true){cout << "This expression is not legal." << endl; }else{/* 将中缀表达式转换为后缀表达式 */for(i = 0; str[i] != '\0'; i++){/* 如果该字符为数字,解析该数字，并压入栈 */if(str[i] >= '0' && str[i] <= '9'){data = https://www.it610.com/article/analyData(str,i); post_str.push_back(data); i--; }else if(str[i] =='('){oper_char.push(str[i]); }else if(str[i] == ')'){char chtemp[2] = {0}; chtemp[0] = oper_char.top(); while(chtemp[0] != '('){string strtemp(chtemp); post_str.push_back(strtemp); oper_char.pop(); chtemp[0] = oper_char.top(); }oper_char.pop(); }else if(str[i] == '+' || str[i] == '-'){char chtemp[2] = {0}; /* 全部出栈，但是碰到 '('就要停止出栈 */while(oper_char.size() != 0){chtemp[0] = oper_char.top(); if(chtemp[0] == '('){break; } oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); } /*将当前的表达式符号入栈*/oper_char.push(str[i]); }else if(str[i] == '*' || str[i] == '/'){char chtemp[2] = {0}; while(oper_char.size() != 0){chtemp[0] = oper_char.top(); if(chtemp[0] == '(' || chtemp[0] == '+' || chtemp[0] == '-'){break; }else{oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); }} /*将当前的表达式符号入栈*/oper_char.push(str[i]); }} /* 存放表达式的栈可能还有数据 */while(!oper_char.empty()){char chtemp[2] = {0}; chtemp[0] = oper_char.top(); oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); } /* 把逆波兰表达式求值 */cout << getTheResult(post_str) << endl; } return 0; }

【C++代码实现逆波兰表达式】以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。