Überprüfung eines mathematischen Terms

Hallo,

meine Aufgabe ist es einen Kellerautomat in C++ zu schreiben, welcher einen mathematischen Term auf Korrektheit überprüft.

Erlaubte Zeichen sind * und +.

Bsp.:
5+22*4 = erlaubt
5 2+3 = nicht erlaubt

Einen einfachen Kellerautomat mit Klammerausdrücken ( { { } } ) zu schreiben war nicht das Problem. Wie sollte ich den Kellerautomat am Besten aufbauen um einen mathematischen Term zu analysieren?

// Kellerautomat mit Klammerausdrücken

#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    const int POP    = -1;
    const int ACCEPT = -2;
    const int ERROR  = -3;

    const int SIZE   = 3;   // Größe des Eingabealphabets

    int states[2][SIZE*2] =
    {
        {
            '(',  1,
            ')',  ERROR,
            '\0', ACCEPT
        },
        {
            '(',  1,
            ')',  POP,
            '\0', ERROR
        }
    };

    char s [80+1];

    int stack[100] = { 0 };
    int i          = 0;
    int action     = 0;
    int* tos       = stack;
    char* p        = s;

    cout<<"Bitte Ausdruck eingeben: ";
    cin>>s;

    *(tos++) = 0;

    do
    {
        action = ERROR;
        for (i = 0; i < SIZE; i++)
        {
            if (states[*(tos-1)][i*2] == *p)
            {
                action = states[*(tos-1)][i*2+1];
                break;
            }
        }

        if (action == ERROR)
        {
            cout<<"Unerwartetes Zeichen an Position "<<p-s<<"!";
            break;
        }

        else if (action == ACCEPT)
        {
            cout<<"Ausdruck akzeptiert!";
            break;
        }

        else if (action == POP)
        {
            tos--;
        }

        else
        {
            *(tos++) = action;
        }

        // Eingabe erweitern
        p++;
    }

    while (action != ACCEPT);

    system("PAUSE");
    return 0;
}

irgendwelche Ideen?

Danke,
methos-

Es handelt sich um einen gültigen Term, wenn nach Jeder Zahl ein Operator und nach jedem Operator eine Zahl auftaucht und am Ende eine Zahl steht.

Dann brauchst du 2 Zustände.

1. letzter Teil war Operator
2. letzter Teil war Zahl

Befindest du dich in Zustand 1. und findest noch einen Operator gibts nen Fehler.
Befindest du dich in Zustand 2. und findest noch eine Zahl gibts nen Fehler.
Befindest du dich am Ende der Terms und bist in Zustand 1., gibts nen Fehler.

Der Rest ergibt dann gültige Terme.

Also so im Groben müsste das so funktionieren

cheopz

Yacc/Bison würde dir die halbe Arbeit abnehmen...

BorisDieKlinge

aber es geht ja um verschachtelte terme oder?

d.h. die Anzhal der "(" und der ")" muzss gleich sein

und die "(" ist immer vor einer Zahl, und ")" ende immer dirket hinter eine zahl sonst fehler..

Walli

BorisDieKlinge schrieb:

und die "(" ist immer vor einer Zahl, und ")" ende immer dirket hinter eine zahl sonst fehler..

Deiner Meinung nach ist also 3*(-25+17) kein zulässiger Ausdruck?

minhen

Streng genommen hat er Zahl und nicht Ziffer gesagt. Im Gegenzug könnte man also dich fragen, ob -25 für dich keine Zahl ist
(Das macht BorisDieKlinges Aussage aber nicht unbedingt richtiger, man denke nur an verschachtelte Klammern.)