資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時裝研究
法律研究用 C++ 程式評估逆波蘭表示式
假設我們有逆波蘭表示式，我們必須評估值。逆波蘭表示式也稱為字尾表示式。這裡我們必須使用棧資料結構來求解字尾表示式。
從字尾表示式中，在找到某些運算數時，將它們放入棧中。找到某個運算子時，從棧中彈出兩個元素，然後按正確的順序執行操作。在那之後，結果也會被放入棧中以備將來使用。而在完成整個表示式後，最終結果也會儲存在棧頂。因此，如果表示式是“53+62/*35*+”，那麼答案將是 39
讓我們看步驟 −
- 對於字尾表示式中的每個字元 ch，執行以下操作
- 如果 ch 是運算子 ☉，則
- a := 彈出棧中的第一個元素，
- b := 彈出棧中的第二個元素
- res := b ☉ a
- 將 res 壓入棧中
- 否則，如果 ch 是一個運算數，則
- 將 ch 新增到棧中
- 如果 ch 是運算子 ☉，則
- 返回棧頂元素
示例（C++）
讓我們看以下實現以獲得更好的理解 −
#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
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){
//Perform operation
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++){
//read elements and perform postfix evaluation
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);
}輸入
"53+62/*35*+"
輸出
The result is: 39
更新日期：2020 年 4 月 28 日
5 千 + 次瀏覽
廣告