JAVAデータ構造-スタック式と中置式の単純な計算機
Java Data Structure Simple Calculator
アドバンストおよびラストアウト、オンおよびオフのデータ構造、 常にスタックの最上位を指すようにポインターを定義します。データがない場合は-1を指定します。
1.配列シミュレーションを使用してスタック定義構造を実装します
class ArrayStack { private int MaxSize //Indicates the maximum space of the stack private int[] array //Indicates an array to store data private int top = -1 // means the top of the stack, the starting position is -1 means no data public ArrayStack(int maxSize) {initialization stack MaxSize = maxSize array = new int[maxSize] }}2.スタック方式
1.データが利用可能な場合、topは0から始まります。 top = maxSize -1 いっぱいになると、2.top = -1のときに空になります。
3.スタックをトッピングするときは、トップを上に移動してから、データをトップポインティング位置に追加します。4。スタックのトップを移動すると、トップが下に移動します。データは実際にはスタックから出ません。ただし、最上位はスタックの最上位を指します。
5.スタックをトラバースするときは、スタックの一番上からトラバースします
public Boolean isFull() {Full when the top of the stack is -1, because top starts from 0 return top == MaxSize - 1 } public Boolean isEmpty() {When top=-1, the stack is empty return top == -1 } Add a piece of data to the stack public void push(int num) { if (isFull()) { System.out.println('Stack is full, can't add ~~') return } top++ array[top] = num } * Pop the top data of the stack and pop the stack public int pop() { if (isEmpty()) { throw new RuntimeException('Stack is empty, can't get out of stack~!') } int value = array[top] top-- return value }2.中置式とスタックの実装単純な計算機
1.プレフィックス式 （3 + 4）×5-6対応するプレフィックス式は次のとおりです。 -×+ 3 4 5 6
。 式を右から左にスキャンします 数値がスタックにプッシュされると、シンボルがポップアップし、number1、number2、およびnumber2の2つの数値がポップアップします。 number1演算子number2を使用する
二。 中置式 に中置式は 一般的な操作式 、といった（3 + 4）×5-6一般的な計算方法
3.3。 接尾辞の表現 （3 + 4）×5-6対応のリアサフィックス式ははい 3 4 + 5×6 -
。 式を左から右にスキャンします 数値がスタックにプッシュされると、シンボルがポップアップし、number1、number2、およびnumber2の2つの数値がポップアップします。 number2演算子number1を使用する
二。 中置式の計算
1.2つのスタックを準備します1.データスタックを保存します2.シンボルスタックを保存します
2.シンボルの場合：1。 シンボルスタックが空です または 現在のシンボルの優先度は、スタックの一番上のシンボルの優先度よりも大きい スタックに直接プッシュされます
2.もし 現在のシンボルの優先度は、スタックの一番上のシンボルの優先度よりも低くなっています 次に、データスタックから2つの数値を取り出します Num1、num2は演算子を取り出します
運をやっている Num2演算子num1 取得する 操作の結果はデータスタックにプッシュされ、新しいシンボルはスタックにプッシュされます
3.最後に、スキャンが完了し、2つのデータを順番に取得し、オペレーターが操作を実行して、結果をスタックに配置します。
データスタックに残っている数値が最終的な計算結果です
式としてリストされている= '3 + 2 * 3-1'
1.最初のスキャンデータスタックは3、2、3、シンボルスタックは+、* 2です。-にスキャンする場合、優先度は*未満です。 データスタックから2つのデータ操作を取得して6を取得し、それをスタックにプッシュします
3.3。 データスタックは3、6、1で、シンボルスタックは+、-、、、、、、、、、、
5.5。 2つのデータを順番に取得し、オペレーターが操作を実行して、結果をスタック6に配置します。最終的なデータスタック番号は8です。