摘要:下面我們用棧來實現簡易的四則運算計算器。列一下本文的思路實現鏈棧的數據結構及其操作中綴表達式轉后綴表達式后綴表達式求值首先先實現一個鏈棧。是否是四則運算符號計算后綴表達式的值為空則跳過最后,我們測試一下所實現的計算器。
棧是一種限定僅在表尾進行插入和刪除操作的線性表。棧的應用有很多,比如常見的遞歸,計算機表達式求值等。下面我們用棧來實現簡易的四則運算計算器。
列一下本文的思路:
實現鏈棧的數據結構及其操作
中綴表達式轉后綴表達式
后綴表達式求值
//定義棧的數據結構 class Node { public $symbol; public $next; public function __construct( $symbol, $next ) { $this->symbol = $symbol; $this->next = $next; } } //初始化棧,生成頭結點 function initStack( &$node ) { $node = new Node( "", null ); } //入棧 function push( Node &$node, $symbol ) { $p = new Node( $symbol, null ); $p->next = $node->next; $node->next = $p; } //出棧 function pop( Node &$node, &$symbol ) { if ( null == $node->next ) { echo "棧空 "; return; } $q = $node->next; $symbol = $q->symbol; $node->next = $node->next->next; unset( $q ); }
//獲取運算符的優先級 function get_priority( $symbol ) { switch ( $symbol ) { case "(": $priority = 3; break; case "*": case "/": $priority = 2; break; case "+": case "-": $priority = 1; break; case ")": $priority = 0; break; default: $priority = 0; break; } return $priority; } //棧頂依次出棧,如果遇到"("則停止 function clear_stack( &$list ) { $res = ""; while ( null != $list->next ) { if ( "(" != $list->next->symbol ) { pop( $list, $item ); $res .= $item; } else { pop( $list, $item ); return $res; } } return $res; } //中綴表達式轉后綴表達式 function middle_to_back( $middle_expression ) { initStack( $list ); $back_expression = ""; $length = strlen( $middle_expression ); for ( $i = 0; $i < $length; $i ++ ) { $symbol = $middle_expression[ $i ]; if ( " " != $symbol ) { if ( is_numeric( $symbol ) ) { //數字直接輸出 $back_expression .= $symbol; } else {//非數字則比較優先級 $stack_top_priority = get_priority( null == $list->next ? "" : $list->next->symbol ); $current_symbol_priority = get_priority( $symbol ); if ( $current_symbol_priority > $stack_top_priority ) {//優先級比棧頂高則進棧 push( $list, $symbol ); } else { $output = clear_stack( $list ); $back_expression .= $output; if ( ")" != $symbol ) { push( $list, $symbol ); } } } } } while ( null != $list->next ) {//將棧清空 pop( $list, $item ); $back_expression .= $item; } return $back_expression; }
//是否是四則運算符號 function is_arithmetic_symbol( $symbol ) { $arithmetic_symbols = array( "+", "-", "*", "/" ); if ( in_array( $symbol, $arithmetic_symbols ) ) { return true; } else { return false; } } //計算后綴表達式的值 function calculate( $expression ) { $stack = new Node( "", null ); $length = strlen( $expression ); for ( $i = 0; $i < $length; $i ++ ) { if ( " " != $expression[ $i ] ) {//為空則跳過 if ( is_numeric( $expression[ $i ] ) ) { push( $stack, $expression[ $i ] ); } else if ( is_arithmetic_symbol( $expression[ $i ] ) ) { pop( $stack, $n1 ); pop( $stack, $n2 ); $res = get_result( $n2, $n1, $expression[ $i ] ); push( $stack, $res ); } else { echo "wrong symbol, exit"; exit(); } } } $value = $stack->next->symbol; return $value; }
function main() { $back_expression = middle_to_back( "((1+2)*3-4) * 5" ); $result = calculate( $back_expression ); echo "后綴表達式的值為: " . $back_expression, PHP_EOL; echo "result : " . $result, PHP_EOL; } main();
得到的結果如下:
簡易的計算器就實現啦!~~~
(代碼中有一些細節未做判斷,希望讀者理解。歡迎大家提出批評修改意見,感謝~)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/29988.html
摘要:采用鏈地址法來處理沖突這個就被賦值到里面去了。的應用非常廣泛,是新框架中用來代替的類,也就是說建議使用,不要使用的方法是同步的,未經同步直接使用對象的中數組默認大小是,增加的方式是。中數組的默認大小是,而且一定是的指數 Hashmap采用鏈地址法來處理沖突: void addEntry(int hash, K key, V value, int bucketIndex) { ...
摘要:棧底是固定的,而棧頂浮動的如果棧中元素個數為零則被稱為空棧。入棧將數據保存到棧頂。鏈棧鏈棧是指棧的鏈式存儲結構,是沒有附加頭節點的運算受限的單鏈表,棧頂指針是鏈表的頭指針。 一、喜歡單挑線性表 1.線性表的特性 線性表是一個線性結構,它是一個含有n≥0個節點的有限序列。在節點中,有且僅有一個開始節點沒有前驅并有一個后繼節點,有且僅有一個終端節點沒有后繼并有一個前驅節點。其他的節點都有且...
摘要:注意當多個父接口中存在相同的默認方法時,子類中以就近原則繼承。定義靜態默認方法這是版簡易計算器接口默認方法使用定義接口并提供默認打印方法定義接口默認方法支持方法形參這是數值運算基本接口。。。 總概 JAVA8 已經發布很久,而且毫無疑問,java8是自java5(2004年發布)之后的最重要的版本。其中包括語言、編譯器、庫、工具和JVM等諸多方面的新特性。 Java8 新特性列表如下:...
閱讀 2472·2021-11-24 09:39
閱讀 3518·2019-08-30 15:53
閱讀 594·2019-08-29 15:15
閱讀 2903·2019-08-26 13:23
閱讀 3212·2019-08-26 10:48
閱讀 643·2019-08-26 10:31
閱讀 748·2019-08-26 10:30
閱讀 2359·2019-08-23 18:32