none
四則運算計算機的相關問題[後序表示法] RRS feed

  • 問題

  • 說明:
    設計一簡易型計算機介面,使用者從該介面輸入四則(加減乘除)運算式後,程式需將原四則運算式與正確結果輸出至檔案(b.txt)中。輸入之四則運算式中需包含有括號以改變運算之優先順序,且可輸入不只一層括號,輸入之數值需可包含浮點數。如輸入之四則運算式含有其他無法辨識的符號(例如
    a、c、$、%、...等),或運算式不合規範(括號數錯誤、括號順序錯誤、運算子錯誤、浮點數格式錯誤、...等),則程式需顯示”運算式有誤!”字樣,且不會產生b.txt檔案。

    <ignore_js_op></ignore_js_op>

    提示:
    平常所使用的運算式,主要是將運算元放在運算子的兩旁,例如:a+b/d,這樣的式子,這稱之為中序(Infix)表示式。對於人類來說,這樣的式子很容易理解,但由於電腦執行指令時是有順序的,遇到中序表示式時,無法直接進行運算,而必須進一步判斷運算的先後順序,所以必須將中序表示式轉換為後序(Postfix)表示式,後序表示式又稱之為逆向波蘭表示式(Reverse
    polish
    notation)。例如:(a+b)*(c+d)這個式子,後序表示式為:ab+cd+*。


    產生b.txt我會,輸入錯誤會顯現出”運算式有誤!”字樣我也OK。
    重點就是卡在四則運算計算機....
    看完提示以後根本崩潰,比沒提示還糟...
    完全不知道該從何下手,也完全不知道後序的意思。

    他的意思是說(5+7)*(9+10)要跑出228,可是如果用成後序表示法,
    那麼要如何做計算?
    57+910+*,這樣怎麼可能跑出228?
    因為從來沒接觸過,所以看不太懂,沒想到多了個括號難度就增加那麼多,
    我會寫計算機,但不會寫四則運算計算機...
    可以給我點參考嗎?
    希望可以用白話文解釋,我真的看不懂網路上的回應...
    拜託各位了!!!

    2013年2月10日 上午 07:28

解答

  • 您可以參考這個範例的做法:Postfix Calculator in C#
    2013年2月10日 上午 09:42
  • 前序,中序與後序是二元樹的基本概念:http://en.wikipedia.org/wiki/Binary_expression_tree

    計算機很常使用這個來做運算,首先就是樹的建立和走訪,這個只要知道流程,程式處理並不難,寫的出樹的建立和走訪後,就能得到後序的指令。

    然後搭配 stack 去做運算,你要的東西就都出來了。

    這裡有一個用 C++ 寫的:http://math.hws.edu/eck/cs225/s03/binary_trees/,其中有一個 Expression Tree 可用來參考。

    寫程式之前,先把流程先搞清楚弄懂,再去寫程式,否則就算想到天荒地老也不可能想的出來...

    PS: 資料結構的教科書很多都有用 tree 寫計算機的範例。


    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 09:45
    版主
  • 這邊有 VBNET 版的範例。

    http://tlcheng.twbbs.org/TLCheng/Net/NetList.aspx?Action=Module&Module=36

    你可以從導論看起。


    論壇是網友平等互助 保證解答請至 微軟技術支援服務


    提問時,錯誤情境描述與錯誤訊息很重要,情境描述包含你做了什麼,預期的結果與實際發生的結果。一個最爛的問法範例:「我的電腦電腦怎麼不能開機?」誰知道你家是不是沒電還是你根本找不到電源鈕。

    2013年2月12日 下午 03:27
  • http://msdn.microsoft.com/zh-tw/ee854988.aspx

    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月13日 上午 07:58
    版主

所有回覆

  • 你的努力在哪裡?

    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 08:17
    版主
  • 您是指我自己所練習的程式碼,
    還是指我自己上網查詢我所不會的地方所做的努力?
    如果是前者,我只會寫文中所敘述的產生b.txt以及輸入錯誤會顯現出”運算式有誤!”字樣。
    至於後者,我所花費的努力已經很久了,解這題已經解了很久,我跟同學討論過,問過老師、上網查過
    但是他們不是不會,就是一堆我看不懂的程式碼,我不知道如何從這些我看不懂的程式碼中獲得東西,
    我問每個問題之前,我自己一定都想過很多,也上網查過,但就是沒有我想獲得的知識,才會來這裡發問,
    如果你需要什麼我練習的證據我在附上來給您。
    2013年2月10日 上午 08:46
  • 想先說一下,我對所謂的Infix Postfix等等並不認識,
    所以是根據你的問題再去尋找些資訊去了解,

    在尋找的時候,在codeproject有看到這個Convert Program
    或許你可以參考以及研究他的程式碼邏輯,看看是否能夠多多少少幫助到你

    請參考
    http://www.codeproject.com/Tips/370486/Converting-InFix-to-PostFix-using-Csharp-VB-NET

    2013年2月10日 上午 09:22
  • 您可以參考這個範例的做法:Postfix Calculator in C#
    2013年2月10日 上午 09:42
  • 前序,中序與後序是二元樹的基本概念:http://en.wikipedia.org/wiki/Binary_expression_tree

    計算機很常使用這個來做運算,首先就是樹的建立和走訪,這個只要知道流程,程式處理並不難,寫的出樹的建立和走訪後,就能得到後序的指令。

    然後搭配 stack 去做運算,你要的東西就都出來了。

    這裡有一個用 C++ 寫的:http://math.hws.edu/eck/cs225/s03/binary_trees/,其中有一個 Expression Tree 可用來參考。

    寫程式之前,先把流程先搞清楚弄懂,再去寫程式,否則就算想到天荒地老也不可能想的出來...

    PS: 資料結構的教科書很多都有用 tree 寫計算機的範例。


    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 09:45
    版主
  • 有用Google Search查詢過嗎?

    中序 後序 C#


    以下為簽名檔,如果你愛拉椅子坐那就是你的問題。
    先查MSDN文件庫
    再用GOOGLE搜尋
    才到論壇來發問

    這是論壇不是技術支援中心
    沒有人得無償解答你的問題

    在標題或文章註明很急
    不會增加網友回覆速度

    2013年2月10日 下午 12:54
  • 先謝謝大家的回覆,
    我會一一看過,這是我所到過的各大論壇回復速度最快的論壇...
    而且都很專業,我希望能在這邊學習各位的知識,進而回答別人的問題,
    很感謝大家願意幫忙,謝謝!
    2013年2月10日 下午 03:18
  • 如果是作業... 老師說啥你做啥。

    如果不是作業... 我建議你直接用動態編譯... 完全不用處理加減乘除及瓜號,引入 Math 類別後,還可以直接用數學函數,變成類似工程計算機那樣~


    論壇是網友平等互助 保證解答請至 微軟技術支援服務


    提問時,錯誤情境描述與錯誤訊息很重要,情境描述包含你做了什麼,預期的結果與實際發生的結果。一個最爛的問法範例:「我的電腦電腦怎麼不能開機?」誰知道你家是不是沒電還是你根本找不到電源鈕。

    2013年2月11日 下午 04:01
  • 不是作業,
    可以在講詳細一點嗎?

    2013年2月12日 上午 08:00
  • 這邊有 VBNET 版的範例。

    http://tlcheng.twbbs.org/TLCheng/Net/NetList.aspx?Action=Module&Module=36

    你可以從導論看起。


    論壇是網友平等互助 保證解答請至 微軟技術支援服務


    提問時,錯誤情境描述與錯誤訊息很重要,情境描述包含你做了什麼,預期的結果與實際發生的結果。一個最爛的問法範例:「我的電腦電腦怎麼不能開機?」誰知道你家是不是沒電還是你根本找不到電源鈕。

    2013年2月12日 下午 03:27
  • http://msdn.microsoft.com/zh-tw/ee854988.aspx

    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月13日 上午 07:58
    版主
  • 我後來用substring判斷,
    可是我卡在一個地方,
    如果用程式碼寫出,如果遇到"("就把後面的數值扔到陣列1(不會寫),
    如果遇到+-*/就把它扔到陣列2(這我會),
    如果遇到")"就把陣列2的運算子扔回來(不會寫)。
    應該是要用IF不過不知道怎麼用...
    還有如何判斷是否為數值...
    以上問題..

    2013年3月1日 上午 11:31
  • 上面很多人給你回應時, 已經給了你很多答案了, 不要再土法煉鋼, 硬解你的問題了.

    如果把一個四則運算排進一棵二元樹裡 (  ), 然後再把用 後序 歷遍時的式子,

    用堆疊處理, 就能算出答案了 (參考 逆波蘭表示式)

    但是排進二元樹是很麻煩的事, 所以就出現了 調度場演算法 , 直接把 四則 變 後序 .

    你參考看看吧, 這些連結都是中文的, 應該能看懂吧.

    下面的 code 能算簡單的整數 +-*/ , 至於 浮點數, 向大家討教.

    out = []
    ops = []
    
    priority = {'+' : 1,
                '-' : 1,
                '*' : 2,
                '/' : 2}
    
    def Shunting_Yard(ex) :
        for i in ex :
            if i in '0123456789' :
                out.append(i)
    
            elif i in ('+', '-', '*', '/') :
                if len(ops) > 0 :
                    try :
                        if priority[i] > priority[ops[0]] :
                            ops.insert(0, i)
    
                        elif priority[i] <= priority[ops[0]] :
                            out.append(ops.pop(0))
                            ops.insert(0, i)
                    except KeyError :
                        ops.insert(0, i)
                else :
                    ops.append(i)
    
            elif i == '(' :
                ops.insert(0, i)
    
            elif i == ')' :
                while ops[0] != '(' :
                    out.append(ops.pop(0))
                    if ops == [] :
                        print 'Shunting_Yard : error at operator !!'
                        return None
    
                ops.pop(0)
                
        while ops != [] :
            out.append(ops.pop(0))
    
        return ''.join(out) 
    
    stack = []
    def Reverse_Polish(ex) :
        for i in ex :
            if i in ('+', '-', '*', '/') :
                a = stack.pop(0)
                b = stack.pop(0)
                c = str(eval(b + i + a))
                stack.insert(0, c)
            else :
                stack.insert(0, i)
    
        if len(stack) > 1 :
            print 'Reverse_Polish : error at expression !!'
            return None
        else :
            return stack.pop(0)
    
    if __name__ == '__main__' :
        ''''''
        ex1 = '5+((1+2)*4)-3'
        print 'calculate :', ex1
        a = Shunting_Yard(ex1)
    
        if a is not None :
            print 'answer :', Reverse_Polish(a)

    其實就是根據這些, 再以 code 寫出的

    調度場演算法步驟

    逆波蘭表示法求值

    btw : 上篇 最佳組合   未見你的回應, 不知進度如何.

    請注意討論區禮儀, 倒不是強迫一定得回應,

    只是惡性循環下, 以後可能會沒人想回應你.



    • 已編輯 Apple I 2013年3月11日 下午 12:08
    2013年3月11日 上午 11:45