为了求解数学表达式,我们需要前缀或后缀形式。将中缀转换为后缀后,我们需要后缀评估算法来找到正确的答案。
在这里,我们还必须使用堆栈数据结构来解决后缀表达式。
从后缀表达式中,找到一些操作数后,将它们压入堆栈。找到某个运算符后,将从堆栈中弹出两个项目,并按正确的顺序执行操作。之后,结果也被压入堆栈中以备将来使用。完成整个表达式后,最终结果也将存储在堆栈顶部。
Input: Postfix expression: 53+62/*35*+ Output: The result is: 39
postfixEvaluation(postfix)
输入:要计算的后缀表达式。
输出: 评估后缀形式后的答案。
Begin for each character ch in the postfix expression, do if ch is an operator ⨀ , then a := pop first element from stack b := pop second element from the stack res := b ⨀ a push res into the stack else if ch is an operand, then add ch into the stack done return element of stack top End
#include<iostream> #include<cmath> #include<stack> using namespace std; float scanNum(char ch) { int value; value = ch; return float(value-'0'); //return float from character } int isOperator(char ch) { if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^') return 1; //character is an operator return -1; //not an operator } int isOperand(char ch) { if(ch >= '0' && ch <= '9') return 1; //character is an operand return -1; //not an operand } float operation(int a, int b, char op) { //执行操作 if(op == '+') return b+a; else if(op == '-') return b-a; else if(op == '*') return b*a; else if(op == '/') return b/a; else if(op == '^') return pow(b,a); //find b^a else return INT_MIN; //return negative infinity } float postfixEval(string postfix) { int a, b; stack<float> stk; string::iterator it; for(it=postfix.begin(); it!=postfix.end(); it++) { //读取元素并执行后缀评估 if(isOperator(*it) != -1) { a = stk.top(); stk.pop(); b = stk.top(); stk.pop(); stk.push(operation(a, b, *it)); }else if(isOperand(*it) > 0) { stk.push(scanNum(*it)); } } return stk.top(); } main() { string post = "53+62/*35*+"; cout << "The result is: "<<postfixEval(post); }
输出结果
The result is: 39