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