രണ്ട് സ്റ്റാക്ക് അൽഗൊരിതം
പ്രസിദ്ധ ഡച്ച് കമ്പ്യൂട്ടർ ശാസ്ത്രകാരനായിരുന്ന എഡ്ഗർ ഡൈക്സ്ട്രാ കണ്ടുപിടിച്ച ഒരു അൽഗൊരിതമാണ് രണ്ട് സ്റ്റാക്ക് അൽഗൊരിതം അഥവാ ഷണ്ടിങ്ങ് യാഡ് അൽഗൊരിതം. ഒരു ഗണിതവാക്യത്തെ നിർദ്ധാരണം ചെയ്യാനുള്ള അൽഗൊരിതമാണിത്. ഗണിതവാക്യത്തെ നിർദ്ധാരണം ചെയ്യാനായി രണ്ട് സ്റ്റാക്ക് ഉപയോഗിയ്ക്കുന്നു : ഒരു സ്റ്റാക്കിൽ സമവാക്യത്തിലെ സംഖ്യകളെയും മറ്റേതിൽ ഗണിതവാക്യത്തിലെ ഓപ്പറേറ്റേറകളെയും (ഗണിതക്രിയാചിഹ്നങ്ങളൾ) സൂക്ഷിയ്ക്കുന്നു. ഈ സ്റ്റാക്കുകളെ യഥാക്രമം സംഖ്യാ സ്റ്റാക്കെന്നും, ഓപ്പറേറ്റർ സ്റ്റാക്കെന്നും വിളിയ്ക്കുന്നു.
ഗണിതവാക്യങ്ങളെ ഇൻഫിക്സ് രീതിയിൽ നിന്ന് റിവേഴ്സ് പോളിഷ് നൊട്ടേഷനിലേക്കോ അബ്സ്ട്രാക്റ്റ് സിന്റാക്സ് ട്രീ രിതിയിലേക്കോ മാറ്റാൻ ഈ അൽഗൊരിതം ഉപയോഗിക്കാവുന്നതാണ്.
അൽഗൊരിതം
[തിരുത്തുക]- ഗണിത വാക്യത്തിലെ ഓരോ വസ്തുക്കളും (സംഖ്യകളോ, ഗണിത ക്രിയാ ചിഹ്നങ്ങളോ ആകാം) ഇടത്തു നിന്നും വലത്തോട്ട് വായിക്കുക.
- ഇപ്പോൾ വായിച്ചത് ഒരു സംഖ്യ ആണെങ്കിൽ, ആ സംഖ്യയെ സംഖ്യാ സ്റ്റാക്കിലേക്ക് ഇടുക(സ്റ്റാക്കിലേയ്ക്ക് പുഷ് ചെയ്യുക)
- ഇപ്പോൾ വായിച്ചത് ഒരു ഗണിത ക്രിയാ ചിഹ്നം ആണെങ്കിൽ, ആ സംഖ്യയെ ഓപ്പറേറ്റർ സ്റ്റാക്കിലേക്ക് ഇടുക(സ്റ്റാക്കിലേയ്ക്ക് പുഷ് ചെയ്യുക)
- ഇപ്പോൾ വായിച്ചത് ഒരു ഇടത് ബ്രാക്കറ്റ് - ( - ആണെങ്കിൽ, അതിനെ അവഗണിയ്ക്കുക.
- ഇപ്പോൾ വായിച്ചത് ഒരു വലത് ബ്രാക്കറ്റ് - ) - ആണെങ്കിൽ, സംഖ്യാ സ്റ്റാക്കിൽ നിന്നും രണ്ട് സംഖ്യകളെയും, ഓപ്പറേറ്റർ സ്റ്റാക്കിൽ നിന്നും ഒരു ഗണിതക്രിയാ ചിഹ്നത്തെയും എടുത്തിട്ട് (പോപ്പ് ചെയ്യുക. സ്റ്റാക്കിൽ നിന്നും പോപ്പ് ചെയ്യുംബോൾ അവസാനം കൂട്ടി ചേർത്ത വസ്തുവായിരിയ്ക്കും ലഭിയ്ക്കുന്നത്), ആ രണ്ട് സംഖ്യകളുടെ മേൽ ഈ ഗണിത ക്രിയ നടത്തി, ലഭിച്ച ഉത്തരത്തെ സംഖ്യാ സ്റ്റാക്കിലേയ്ക്ക് ഇടുക(പുഷ് ചെയ്യുക)
- സമവാക്യത്തിന്റെ വലത്തേ അറ്റം എത്തുന്നതു വരെ അഥവാ സമവാക്യം തീരുന്നത് വരെ, പടി 1-5 വരെ കൊടുത്തിരിയ്ക്കുന്ന കാര്യങ്ങൾ ആവർത്തിയ്ക്കുക. സംഖ്യാ സ്റ്റാക്കിൽ അവസാനിയ്ക്കുന്ന സംഖ്യ ആയിരിയ്ക്കും ഗണിത സമവാക്യത്തിനെ നിർദ്ധാരണം ചെയ്താൽ ലഭിയ്ക്കുന്ന ഉത്തരം
പ്രാധാന്യം
[തിരുത്തുക]ഡൈക്സ്ട്രായുടെ രണ്ട് സ്റ്റാക്ക് അൽഗൊരിതത്തിൽ ഗണിതക്രിയകളുടെ മുൻ ഗണനാക്രമം കൂടെ നിശ്ചയിച്ചാൽ ലെക്സിക്കൽ അനലൈസറിന്റെയും, പാർസറിന്റെയും, കമ്പൈലറിന്റെയും ഒക്കെ പ്രാഥമികരൂപം ലഭിയ്ക്കും. ആ പഠനങ്ങളെയൊക്കെ സഹായിച്ചിട്ടുണ്ട് ഈ അൽഗൊരിതം.