使用堆栈计算表达式的 C++ 程序
为了求解数学表达式,我们需要前缀或后缀形式。将中缀转换为后缀后,我们需要后缀评估算法来找到正确的答案。
这里我们也必须使用堆栈数据结构来解决后缀表达式。
从后缀表达式中,当找到一些操作数时,将它们压入堆栈。当找到某个运算符时,从堆栈中弹出两个项目,然后按正确的顺序执行操作。之后,结果也被压入堆栈以备将来使用。完成整个表达式后,最终结果也存入栈顶。
Input: Postfix expression: 53+62/*35*+ Output: 结果是: 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#include #include using namespace std; float scanNum(char ch) { int value; value = ch; return float(value-'0'); //从字符返回浮点数 } int isOperator(char ch) { if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^') return 1; //字符是一个运算符 return -1; //不是运营商 } int isOperand(char ch) { if(ch >= '0' && ch <= '9') return 1; //字符是一个操作数 return -1; //不是操作数 } 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); //找到b^a else return INT_MIN; //返回负无穷大 } float postfixEval(string postfix) { int a, b; stack 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 << "结果是: "< 输出结果 结果是: 39