2015-10-29 73 views
0

,以創建一個計算器,我使用了Java程序的調度場算法(https://en.wikipedia.org/wiki/Shunting-yard_algorithm)。我差不多完成了,但我仍然需要執行功能。我遇到了一個問題:我想讓計算器在放到一起時自動乘以像x和y這樣的變量 - 例如:計算器將xy轉換爲x * y。另外,我希望計算器將(x)(y)轉換爲(x)*(y)和x(y)爲x *(y)。我已經做了所有的這種使用下面的代碼:分流碼功能

infix = infix.replaceAll("([a-zA-Z])([a-zA-Z])", "$1*$2"); 
infix = infix.replaceAll("([a-zA-Z])\\(", "$1*("); 
infix = infix.replaceAll("\\)\\(", ")*("); 
infix = infix.replaceAll("\\)([a-zA-Z])", ")*$1"); 

(在我的計算器,變量名總是單個字符)
這現在的偉大工程,但是當我實現的功能這個意願,當然,不行。它會將「sin(1)」變成「s * i * n *(1)」。我怎樣才能使這個代碼做乘法轉換隻爲運營商,而不是功能?

回答

3

預處理輸入解析並不是實現你想要什麼好辦法。文本替換無法知道解析算法知道什麼,並且您也丟失了原始輸入,這對打印有用的錯誤消息很有用。

相反,你應該根據上下文決定做什麼。保持先前解析的令牌的類型爲輸入開頭的特殊類型。

如果前一個標記是一個值標記–一個數字,一個變量名稱或一個子表示–的結束標記,當前一個是值標記也發出一個額外的乘法運算符。如果負的價值代幣否則否定後,發現這是一個減法:

同樣的邏輯也可以用來確定一個減號是否是一元的否定或二進制減法。

您的想法將x(y)轉換爲x * (y)當然會與函數調用語法衝突。

0

我們可以把它分成兩部分。有一個用於括號表達式的規則,另一個用於乘法。

而不是維基百科文章,這是故意爲了解釋的目的而簡化的文章,我會按照Parsing Expressions by Recursive Descent這個更詳細的例子來處理括號內的表達式。

這是我用我的解析器可以與隱含乘法工作的代碼。我有多字母變量名稱,並使用空格來分隔不同的變量,所以你可以有「2 pi r」。

protected void expression() throws ParseException { 
    prefixSuffix(); 
    Token t = it.peekNext(); 
    while(t!=null) { 
     if(t.isBinary()) { 
      pushOp(t); 
      it.consume(); 
      prefixSuffix(); 
     } 
     else if(t.isImplicitMulRhs()) { 
      pushOp(implicitMul); 
      prefixSuffix(); 
     } 
     else 
      break; 
     t=it.peekNext(); 
    } 
    while(!sentinel.equals(ops.peek())) { 
     popOp(); 
    } 
} 

這需要一些其他功能。

我使用一個單獨的標記化步驟,其破壞了輸入到離散的令牌。 Tokens類有許多方法,尤其是Token.isBinary()測試如果運算符是二元運算符,如+,=,*,/。另一種方法Token.isImplicitMulRhs()測試令牌是否可以出現在隱式乘法的右側,這對於數字,變量名稱和左括號是成立的。

Iterator<Token>用於輸入流。 it.peekNext()查看下一個令牌,並且it.consume()移至輸入中的下一個令牌。

pushOp(Token)將令牌推入運算符堆棧,popOp刪除一個和。pushOp具有處理不同運算符優先級的邏輯。彈出操作者如果它們具有較低的優先級特別值得注意

protected void pushOp(Token op) 
{ 
    while(compareOps(ops.peek(),op)) 
     popOp(); 
    ops.push(op); 
} 

的是implicitMul人工令牌具有相同優先級的乘法,其被壓入操作棧。

prefixSuffix()處理表達式,它可以是數字和帶有可選前綴的後綴運算符的變量。這將識別「2」,「x」,「-2」,「x ++」,從輸入中刪除令牌並將其添加到輸出/運算符堆棧中。

我們可以認爲這個程序在BNF作爲

<expression> ::= 
      <prefixSuffix> (<binaryOp> <prefixSuffix>)* // normal binary ops x+y 
      | <prefixSuffix> (<prefixSuffix>)* // implicit multiplication x y 

處理括號prefixSuffix()完成。如果檢測到左括號,則它將遞歸調用expression()。爲了檢測匹配的右括號,特殊的哨兵令牌被壓入操作員堆棧。當在輸入中遇到右括號時,主循環會中斷,並且操作員堆棧上的所有操作員都會彈出,直到遇到標記並且控制返回到prefixSuffix()。代碼可能類似於

void prefixSuffix() { 
    Token t = it.peekNext(); 
    if(t.equals('(')) { 
     it.consume(); // advance the input 
     operatorStack.push(sentinel); 
     expression(); // parse until ')' encountered 
     t = it.peekNext(); 
     if(t.equals(')')) { 
      it.consume(); // advance the input 
      return; 
     } else throw Exception("Unmatched ("); 
    } 
    // handle variable names, numbers etc 
} 
0

另一種方法可能是使用標記,類似於解析器的工作方式。

第一階段是將輸入文本轉換爲一個標記列表,這些標記列表是表示找到的實體類型及其值的對象。 例如,你可以有一個變量標記,它的值是變量的名字('x','y'等等),開放或閉括號的標記等。 因爲我假設你知道提前計算器可以使用的函數的名稱,您還將擁有一個函數令牌,其值是函數名稱。 因此,令牌化階段的輸出會區分變量和函數。

實現,這不是太硬,只是一直嘗試首先匹配函數名, 所以「罪」將被識別爲一個功能,而不是作爲三個變量。

現在第二階段可以插入缺失的乘法運算符。這會不會現在是困難的,因爲你知道你只需插入他們之間:

{VAR,RIGHT_PAREN}和{VAR,LEFT_PAREN,功能}

但從來沒有功能和LEFT_PAREN之間。