中置式をメモリ内の式ツリーに変換するコードがあります。これはうまくいきます。小さなトラブルが 1 つだけあります。単項演算子 (正しい連想演算子) を正しく使用する方法を接続するだけです。
次の中置式を使用:
+1 + +2 - -3 - -4
私は次のRPNを期待します：
1+2++3-4--
しかし、私が見つけることができるオンラインの中置後置変換ツールはどれも、私が期待する方法でこの例を処理することはできません。右結合演算子、特に単項演算子と間違われる可能性のある二項演算子の処理について明確な説明がある人はいますか?
編集/明確化:中置から後置への変換中に単項演算子を処理する方法を知りたいです。つまり、たとえば、同じ「-」文字を二項演算子ではなく単項として認識し、優先順位が異なります。おそらく2つの状態を持つステートマシンを使用することを考えますが...?
さて、解析段階で、特定の演算子がバイナリ/単項であるかどうかを判断する必要があります。これを行うと、RPNを作成するときに、2つまたは1つの引数を取るように演算子にタグを付けることができます。
単項演算子でも機能するように設計された、操車場アルゴリズムを使用して解析（および同時にRPNの作成）を実行してみることができます。
いずれにせよ、気になるのが単項+または-だけの場合は、「予期せず」に表示される+または-が表示されたら、角かっこで0を挿入できます。
例えば
+1 + +2 - -3 - -4
あなたはそれを通過して変換することができるはずです
(0+1) + (0+2) - (0-3) - (0-4)
これで、単項+または-について心配する必要はなく、演算子が取る引数の数で演算子にタグを付けることをおそらく忘れることができます。
この混沌とした C# コードが役立つかもしれません。単項演算子は算術演算で最大の優先順位を持っているため、優先順位は高くなります。単項演算子を識別するために、各演算子トークンの後に true に設定され、オペランドの後に false に設定される boolean 変数 unary を使用しました。PFE で単項演算子と二項演算子を区別できるように、単項プラス演算子とマイナス演算子には別の表記法を使用する必要があります。ここで、'#' と '~' は、後置式 (PFE) で単項プラスと単項マイナスを表すために使用されます。
このアプローチを使用すると、1+-1,1+(-1),1---1,1+--1 のようなすべてのケースを処理できます。
using System;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DSA
{
class Calculator
{
string PFE;
public Calculator()
{
Console.WriteLine("Intializing Calculator");
}
public double Calculate(string expression)
{
ConvertToPost(expression);
return CalculatePOST();
}
public void ConvertToPost(string expression)
{
expression = "(" + expression + ")";
var temp = new DSA.Stack<char>();
string ch = string.Empty;
bool unary = true;
char a;
foreach (var b in expression)
{
a = b;
if (!a.IsOperator()) {
ch += a.ToString();
unary = false;
}
else
{
if (ch!=string.Empty)
PFE += ch+",";
ch = string.Empty;
if(a!='(' && a!=')')
{
if (unary == true)
{
if (a == '-') a = '~'; else if (a == '+') a = '#'; else throw new InvalidOperationException("invalid input string");
}
try
{
if (a.Precedence() <= temp.Peek().Precedence())
{
PFE += temp.Pop().ToString() + ",";
}
}
catch(InvalidOperationException e)
{
}
temp.Push(a);
unary = true;
}
if (a == '(') { temp.Push(a);}
if(a==')')
{
for(char t=temp.Pop();t!='(';t=temp.Pop())
{
PFE += t.ToString() + ",";
}
}
}
}
}
public double CalculatePOST()
{
var eval = new Stack<double>();
string ch = string.Empty;
bool skip = false;
foreach(char c in PFE)
{
if(!c.IsOperator())
{
if (c == ',')
{
if (skip == true)
{
skip = false;
continue;
}
eval.Push(Double.Parse(ch));
ch = string.Empty;
}
else ch += c;
}
else
{
if (c == '~')
{
var op1 = eval.Pop();
eval.Push(-op1);
}
else if (c == '#') ;
else
{
var op2 = eval.Pop();
var op1 = eval.Pop();
eval.Push(Calc(op1, op2, c));
}
skip = true;
}
}
return eval.Pop();
}
private double Calc(double op1, double op2, char c)
{
switch(c)
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '%':
return op1 % op2;
case '/':
return op1 / op2;
case '^':
return float.Parse(Math.Pow(op1,op2).ToString());
default:
throw new InvalidOperationException();
}
}
}
public static class extension
{
public static bool IsOperator(this char a)
{
char[] op = {'+','-','/','*','(',')','^','!','%','~','#'};
return op.Contains(a);
}
public static int Precedence(this char a)
{
if (a == '~' || a== '#')
return 1;
if (a == '^')
return 0;
if (a == '*' || a == '/' || a=='%')
return -1;
if (a == '+' || a == '-')
return -2;
return -3;
}
}
}