リンク リスト スタックを使用して、中置表記の方程式を後置表記に変換するプログラムを作成します。プログラムのスタック部分は独自のクラスであり、独自のヘッダー ファイルにあり、正しく実装されています (私の教授から提供されたテスト メインをコンパイルして実行できます)。現在、継承されたクラスでインフィックス文字列をポストフィックス文字列に変換する実際の関数に取り組んでいます。次のコードがありますが、奇妙な出力が得られるため、どこかで分流場アルゴリズムを間違って実行したと思います。
template <class myType>
void infixToPostfix<myType>::convertToPostfix()
{
linkedStack<char> newS; //creating a new char stack
string output; //creating the postfix output string
for(int i = 0; i < infx.length(); i++) //cycle through the entire string
{
if (isgraph(infx[i])) //skip spaces
{
if (isalpha(infx[i])) //if the char is a letter (caps or uncaps)
{
output += infx[i]; //append it to output
}
else
{
if (newS.isEmptyStack()) newS.push(infx[i]);
else if (precedence(infx[i], newS.top()) //check if the current char has higher precedence than the top of the stack, or if the stack is empty
{
newS.push(infx[i]); //push the current char onto the stack
}
else if (infx[i] == ')') //check if the current char is a closing paren
{
for(;;)
{
if (newS.isEmptyStack()) break;
if (newS.top() != '(') //check if the top of the stack isn't an open paren
{
output += newS.top(); //append the top of the stack to the output
newS.pop(); //pop the top of the stack off
}
else //the top of the stack is a (
{
newS.pop(); //pop the ( off the stack
break; //break out of the for loop
}
}
}
else //the current char doesn't have higher precedence than the top of the stack
{
output += newS.top(); //append to the top of the stack to output
newS.pop(); //pop off the top of the stack
newS.push(infx[i]); //put the current char onto the top of the stack
}
}
}
}
while (!newS.isEmptyStack()) //not sure if this works, assuming we're at the end of the line at this point, and if there's anything on the stack we need to append it to the output
{
output += newS.top();
newS.pop();
}
pfx = output; //setting pfx to the output (pfx is the class variable for the postfix output)
}
後置文字列を表示する私の関数は次のとおりです
template <class myType>
void infixToPostfix<myType>::showPostfix()
{
cout << "Postfix Expression: " << pfx << endl;
}
プログラムを実行すると、次の出力が得られます。
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ ./a.out testinput1.txt
Infix Expression: A + B - C
-ostfix Expression: AB+C
Infix Expression: A + B * C
*+stfix Expression: ABC
Infix Expression: A * B + C / D
/+stfix Expression: AB*CD
Infix Expression: (A + B) * C
*+(tfix Expression: AB)C
Infix Expression: A * (B + C) / D
/+(tfix Expression: A*BC)D
Infix Expression: (A + B) * (C - D)
-(+(fix Expression: AB)*CD)
Infix Expression: A * (B + C / D)
/+(tfix Expression: A*BCD)
Infix Expression: A + ((B + C) * (E - F) - G) / (H - I)
-(--(+( Expression: A+(BC)*EF)G)/HI)
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$
正直なところ、後置式の奇妙なビットのように見えるものが、cout の文字列にプッシュされる理由がわかりません。ヒント/ヘルプはありますか？
編集: ymett によって提案された変更を行った後の私の出力は次のとおりです。私は今、括弧を処理しようとしてどこが間違っていたのかを理解しようとしています。
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ ./a.out testinput1.txt
Infix Expression: A + B - C
Postfix Expression: AB+C-
Infix Expression: A + B * C
Postfix Expression: ABC*+
Infix Expression: A * B + C / D
Postfix Expression: AB*CD/+
Infix Expression: (A + B) * C
Postfix Expression: AB)C*+(
Infix Expression: A * (B + C) / D
Postfix Expression: A*BC)D/+(
Infix Expression: (A + B) * (C - D)
Postfix Expression: AB)*CD)-(+(
Infix Expression: A * (B + C / D)
Postfix Expression: A*BCD)/+(
Infix Expression: A + ((B + C) * (E - F) - G) / (H - I)
Postfix Expression: A+(BC)*EF)G)/HI)-(--(+(
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$