資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的字首表示式的求值
在本文中，我們將討論字首表示式的求值。
字首表示式
在這種表示法中，運算子位於運算元之前，即運算子寫在運算元前面。例如，+ab。這等價於它的中綴表示法a + b。字首表示法也稱為波蘭表示法。
示例
* + 6 9 - 3 1
字首表示式的求值速度快於中綴表示式。此外，字首表示式中沒有括號，這使得它能夠更快地進行求值。
求值字首表示式的演算法
字首表示式的求值需要一個棧資料結構。我們將把運算子壓入棧中，然後求解表示式。
我們將逐個訪問表示式的每個元素。如果當前元素是運算元，我們將將其壓入棧中。如果它是運算子，我們將彈出兩個運算元，執行運算，運算元 運算子 運算元，然後將結果壓回棧中。
演算法 -
步驟 1：從表示式的最後一個元素開始。
步驟 2：檢查當前元素。
步驟 2.1：如果它是運算元，則將其壓入棧中。
步驟 2.2：如果它是運算子，則從棧中彈出兩個運算元。執行運算並將結果壓回棧中。
步驟 3：重複此過程，直到遍歷完表示式的所有元素，並返回棧頂元素，該元素將是運算結果。
讓我們看看我們的演算法如何解決一個字首表示式，
字首表示式：
* + 6 9 - 3 1
迭代：1
掃描的元素 => 1
操作 => 壓入棧
棧=> 1
迭代：2
掃描的元素 => 3
操作 => 壓入棧
棧=> 3 , 1
迭代：3
掃描的元素 => -
操作 => 從棧中彈出兩個元素，執行運算並將結果壓回棧中。
3 - 1 = 2
棧=> 2
迭代：4
掃描的元素 => 9
操作 => 壓入棧
棧=> 9 , 2
迭代：5
掃描的元素 => 6
操作 => 壓入棧
棧=> 6, 9 , 2
迭代：6
掃描的元素 => +
操作 => 從棧中彈出兩個元素，執行運算並將結果壓回棧中。
6 + 9 = 15
棧 => 15 , 2
迭代：7
掃描的元素 => *
操作 => 從棧中彈出兩個元素，執行運算並將結果壓回棧中。
15 * 2 = 30
棧=> 30
結束 => 返回棧頂元素，結果 = 30。
程式說明我們解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
}輸出 -
The result of evaluation of expression *+69-31 is 30
14K+ 次瀏覽
