C++的逆波兰表达式的求解数据结构和算法

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林（Charles Hamblin）在1960年代中期扩充在1960和1970年代，逆波兰记法广泛地被用于台式计算器，因此也在普通公众（工程、商业和金融领域）中使用（百度百科）。算法：
一、将中缀表达式转换成后缀表达式算法：
1、从左至右扫描一中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号"("，则直接存入运算符堆栈。
(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
二、逆波兰表达式求值算法：
1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。

#include #include #include #include "ChainStack.cpp" using namespace std; string reverseConvert(const string& inputString); //将中序表达式转换成逆波兰表达式 int calculateString(const string& inputString); //将逆波兰表达式求解 bool isNumber(const char e); //判断字符是否为数字 bool isSymbol(const char e); //判断字符是否为符号 bool checkLevel(const char c1, const char c2); //c1的运算级别小于c2；返回true; int levelSymbol(const char c1); //返回符号的级别 int main() { string Input = "2*(1+2/2) "; string Output = reverseConvert(Input); cout << Input << endl; cout << Output << endl; cout << "2*(1+2/2 = " << calculateString(Output) << endl; return 0; }int calculateString(const string& inputString) { ChainStack resultStack; string temp = inputString; string::iterator i = temp.begin(); for (; i !=temp.end(); ++i) { if (isNumber(*i)) { resultStack.Push(*i); } else { char t1, t2; int result; resultStack.Pop(t1); resultStack.Pop(t2); if (*i=='+') { result = (t2 - '0') + (t1 - '0'); resultStack.Push(result+'0'); } if (*i == '-') { result = (t2 - '0') - (t1 - '0'); resultStack.Push(result + '0'); } if (*i == '*') { result = (t2 - '0') * (t1 - '0'); resultStack.Push(result + '0'); } if (*i == '/') { result = (t2 - '0') / (t1 - '0'); resultStack.Push(result + '0'); } if (*i == '%') { result = (t2 - '0') % (t1 - '0'); resultStack.Push(result + '0'); } } } char topChar; resultStack.GetTop(topChar); return topChar-'0'; } bool isNumber(const char e) { bool temp = false; switch (e) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': temp = true; break; default: break; } return temp; } bool isSymbol(const char e) { bool temp = false; switch (e) { case '+': case '-': case '*': case '/': case '(': case ')': case '%': temp = true; break; default: break; } return temp; } int levelSymbol(const char c1) { int i = 0; if (c1 == '+' || c1 == '-') { i = 1; } if (c1 == '*' || c1 == '/' || c1 == '%') { i = 2; } return i; } bool checkLevel(const char c1, const char c2) { return levelSymbol(c1) <= levelSymbol(c2); }string reverseConvert(const string& inputString) { ChainStack tempStack; string temp, returnString; char topChar; temp = inputString; string::iterator i = temp.begin(); for (; i != temp.end(); ++i)//从左至右扫描中缀表达式 { tempStack.GetTop(topChar); if (isNumber(*i)) { returnString += *i; } else { if (isSymbol(*i))//若读取的是运算符 { if (*i == '(')//该运算符为左括号"("，则直接存入运算符堆栈。 { tempStack.Push(*i); } else{ if (*i == ')')//该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。 { while (topChar != '(') { tempStack.Pop(topChar); returnString += topChar; tempStack.GetTop(topChar); //运算完后重新获取栈顶元素 } tempStack.Pop(topChar); //把topChar='（'弹出栈 } else { tempStack.GetTop(topChar); if (topChar == '(' || tempStack.Empty())//若运算符堆栈栈顶的运算符为左括号或者为空栈，则直接存入运算符堆栈。 { tempStack.Push(*i); } //若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈 else{ while (checkLevel(*i, topChar))//如果当前符合*i比栈顶符号topChar的运算级低或者相等 { tempStack.Pop(topChar); //将栈顶元素弹出赋给输出串，直到栈顶符合的运算级小于等于当前符号 returnString += topChar; if(!tempStack.GetTop(topChar)) break; //如果栈为空跳出循环 //tempStack.Push(*i); } tempStack.Push(*i); //把当前符号压入栈中 } } } } } } while (!tempStack.Empty()) { tempStack.Pop(topChar); returnString += topChar; } return returnString; }

上述算法有一个缺点:不能计算大于九的数，因为大于九，其数字用字符表示为两个或者更多个字符，在操作的时候有所不同。可以在下次复习使用string的时候写出。