Hola, tengo que elaborar un programa que "Analizar si una frase capturada por el usuario está bien escrita en español." es decir; si el usuario escribe "El coche es azul", es correcto, pero si escribe "El azul es coche", es incorrecto.

No se me ha ocurrido mucho, OJO. No tengo que usar apunteros, ni recursividad (ya que no se ha visto en el curso), ni archivos, solo es el uso de cadenas y todo lo demás, a excepción de lo antes mencionado...

¿Alguna idea?

Sí, claro tengo que tomar en cuenta esas limitaciones y restricciones que mencionas... Pero... ¿Cómo validar? No aterrizo mi idea.

Más o menos como te dice YreX-DwX.
Sin embargo considero que es demasiado complejo para un estudiante.

Además si no está acotado como te han señalado, la complejidad de sale de madre para un 'ejercicio'... realmente es un problema que podría llevar más de un año (varias personas), pués se está pidiendo nada más ni nada menos que analizar semánticamente si una frase es un idioma humano es válida.

De hecho tan solo recoger y categorizar cada palabra del dicionario ya llevaría un tiempo enorme. Ahora bien si se dispone de ese diccionario, la cosa cambia y podría ser asumible.

- Lo primero es un análisis léxico, para obtener los tokens (palabras al caso), determinar si existen en ese diccionario o no, y en caso de que existan asignarles el atributo correspondiente (nombre verbo, adjetivo), etc... Este análisis es el más sencillo. Aunque en español se complica, ya que aunque tengas una buena lista por ejemplo de verbos, como estén conjugados, nuevamente se complica...
- Luego le toca un análisis sintáctico, para comprobar que la frase es admisible: "pajaro un tengo" no es válido, aun cuando cada token es válido. El español admite muchas formas de ordenar las frases con el simple propósito de dar énfasis a alguna parte, lo que complica en exceso dicho análisis... es preciso especificar todas las formas válidas de ordenar nombres artículos, verbos, pronombres, etc...
Me encanta la famosa frase:
     Del salón | en el ángulo oscuro, | de su dueño | tal vez | olvidada, | silenciosa | y | cubierta de polvo, | hallábase | el arpa.
Esta frase ni más  ni menos ejemplifica la complejidad por cuento está expuesta en orden inverso a como la diríamos normalmente:
     El arpa | se hallaba | cubierta de polvo | y | silenciosa, | olvidada | tal vez | de su dueño | en el ángulo oscuro | del salón.
- Finalmente el análisis semántico, aún es un problema en fase de resolución, por la explosión combinatoria del lenguaje humano. Si un lenguaje de programacion apenas tiene entre unas decenas y unas centenas de palabras reservadas, y resulta complejo, cuanto más el lengueja humano que rondan por encima de las 100.000 palabras sin contar variaciones de sus accidentes: número, género, tiempo, etc...
Es decir una frase como la que ponías: "El azul es coche" que señalabas es fácil de resolver desde el analizador sintáctico, pero la frase: "El perro es azul" "el perro come coches", son sintácticamente correcta, exige el análisis semántico... y ahí es donde radica la complejidad... no hay definición-reglas aplicables (que el sentdo común del conocimiento humano) sobre si los perros pueden o no ser azules, y sobre si pueden o no comer coches...

En definitiva, o tienes algunas severas restricciones del tipo: Utilizar solo estos elementos y como máximo 1 de cada tipo: 'articulo, nombre, verbo, adjetivo.  ...o no me creo que sea un ejercicio que te haya mandado ningún profesor, salvo que sea "el profesor chiflado" (I.E. el genial Cantinflas).