4. 中置表示法(infix notation) 轉後置表示法(postfix notation)

想不出來的話就直接幹AST

// (6+2)*5-8/4

int lvl(string s)
{
    if(s=="(")return -100;
    return s == "+" || s == "-" ? 0 : 1;
}

while (true)
{
    var k = Console.ReadLine();
    List<string> segs = new List<string>();
    foreach (var item in k)
    {
        if (item == ' ') continue;
        if (Char.IsDigit(item))
        {
            if (segs.Count == 0 || !Char.IsDigit(segs.Last()[0]))
            {
                segs.Add("");
            }
            segs[segs.Count - 1] = segs.Last() + item;
            continue;
        }
        segs.Add(item + "");
    }

    List<string> o = [];
    Stack<string> ops = [];
    foreach (var item in segs)
    {
        if (char.IsDigit(item[0]))
        {
            o.Add(item);
            continue;
        }
        if (item == "(")
        {
            ops.Push(item);
            continue;
        }
        if (item == ")")
        {
            while (ops.Peek() != "(")
            {
                o.Add(ops.Pop());
            }
            ops.Pop();
            continue;
        }
        while (ops.Count != 0 && lvl(ops.Peek()) >= lvl(item))
        {
            o.Add(ops.Pop());
        }
        ops.Push(item);
    }
    o.AddRange(ops);
    Console.WriteLine(string.Join(" ", o));
}

AST

while (true)
{
    List<string> parseToken(string s)
    {
        List<string> list = new List<string>();
        string numberBuffer = "";
        foreach (var item in s)
        {
            if (item == ' ') continue;
            if (char.IsDigit(item))
            {
                numberBuffer += item;
            }
            else
            {
                if (numberBuffer != "")
                {
                    list.Add(numberBuffer);
                    numberBuffer = "";
                }
                list.Add(item.ToString());
            }
        }
        if (numberBuffer != "")
        {
            list.Add(numberBuffer);
        }
        return list;
    }

    var tokens = parseToken(Console.ReadLine());
    var idx = 0;
    string nextToken()
    {
        if (idx >= tokens.Count) return null;
        return tokens[idx++];
    }

    object factor()
    {
        var token = nextToken();
        if (token == null)
        {
            return null;
        }
        if (token == "(")
        {
            var v = pm();
            idx++;
            return v;
        }
        return int.Parse(token);
    }

    object multiplyDivide()
    {
        var l = factor();
        var next = nextToken();
        while (next == "*" || next == "/")
        {
            var r = factor();
            if (r != null)
            {
                l = (l, next, r);
            }
            else break;
            next = nextToken();
        }
        idx--;
        return l;
    }

    object pm()
    {
        var l = multiplyDivide();
        var next = nextToken();
        while (next == "+" || next == "-")
        {
            var r = multiplyDivide();
            if (r != null)
            {
                l = (l, next, r);
            }
            else break;
            next = nextToken();
        }
        idx--;
        return l;
    }

    string doOn(object k)
    {
        if (k is int)
        {
            return k.ToString();
        }
        var (l, op, r) = ((object, string, object))(k);
        return doOn(l) + " " + doOn(r) + " " + op;
    }
    Console.WriteLine(doOn(pm()));
}