I am in the process of creating a JS function to convert the mathematical
arrangement of InFix (algebraic entry) to PostFix (RPN entry). I will be using
this function in another project I am working on.
The code below works for my needs while developing the function,
but I would like to make two improvements.
1. If a formula has too many ‘( )’ pairs, as in the test button ‘N5’,
the last ‘(‘ entry is posted to the return value. I’m pretty sure that the problem
is in the last step where the remaining operators are popped from the stack,
[code=php]
while ((Stk.length-1) > -1) { // 7)
Tch = Stk.pop(); if (Tch != ‘(‘) { PostStr += Tch + ‘ ‘; }
}
Any ideas on how to change the logic to check for this condition?
It adds the ‘(‘ to the last of the PostFix string. This is just an extra pair
for the algebraic grouping and I can eliminate the problem by removing
the extra outside ‘( )’ combination, but I would like it to recognize that
this is not a problem and just drop the extra ‘(‘ from the stack.
2. I tried to put a forced quote into the code for the ‘T3’ button,
[code=php]
<!– produces error –>
<button id=’t3′ onClick=”getEl(‘inStr’).value = ‘”Now is the time”‘”>T3 error</button>
<!– –>
but as soon as I click on the button, it gives me an error of ‘unterminated string literal’.
Can anyone see where my button assignment is going wrong?
Here is the script that I am using:
[code=php]
<html>
<head>
<title>Infix to Postfix</title>
<script type=”text/javascript”>
function getEl(IDS) { return document.getElementById(IDS); }
function ALERT(msg) {
ans = confirm(msg+’nContinue?’);
return ans;
}
function Toggle(Info) {
var CState = document.getElementById(Info);
if (CState.style.display == “none”) { CState.style.display = “block”; }
else { CState.style.display = “none”; }
}
var Scan = new Array();
function Step1(Str) { // Step 1
var strArr = new Array();
strArr = Str.split(/(w+|d+|W)/); // puts space between each operand/operator
// strArr = Str.match(/(w+|d+|W)/g); // without whitespace
var str = strArr.join(‘ ‘);
str = str.replace(/s+/g,’ ‘);
strArr = str.split(‘ ‘);
strArr.shift(); // drop first blank element
Scan = strArr;
return strArr.join(” “);
}
var Stk = new Array(); // Step 2
var Operators = ‘(,+,-,*,/,’;
var precedence = ‘0,2,2,4,4,’
function Step3() { // Step 3
var PostStr = ”; var cmmd = ”
var Sch = ”; var Tch = ”; Stk = new Array();
var pSch = ‘0’; var pTch = ‘0’;
var Action = ”; var TOS = ”;
var tmp = ”;
for (i=0; i<Scan.length; i++) {
cmmd = Scan[i]; // 1) parse input
Sch = Operators.indexOf(cmmd+’,’);
pSch = ‘0’; if (Sch != -1) { pSch = precedence.charAt(Sch); } // get precedence scanned char
Tch = ”; pTch = ”;
if (!isNaN(Number(cmmd))) { Action = ‘Operand’; } // 2) found number
else { Action = cmmd; } // may be operator
if (Operators.indexOf(cmmd+’,’) == -1) { Action = ‘Operand’; } // variable, not operator
if (cmmd == ‘)’) { Action = cmmd; }
// alert(‘cmmd: ‘+cmmd+’nAction: ‘+Action);
switch (Action) {
case ‘Operand’ : // 2) put number or variable to postfix
PostStr += cmmd + ‘ ‘; break;
case ‘(‘: // 3)
Stk.push(cmmd); break;
case ‘)’: // 5)
do { PostStr += Stk.pop()+’ ‘;
} while ((Stk[Stk.length-1] != ‘(‘) && ((Stk.length-1) != -1));
Stk.pop(); break;
default: // 4)
CommandParse: do {
if (Stk.length < 0) { Stk.push(cmmd); break CommandParse; } // 4a)
Tch = ”; pTch = ‘0’;
if (TOS == ‘(‘) { Stk.push(cmmd); break CommandParse; } // 4b)
Tch = Operators.indexOf(TOS+’,’); // priority of stack character
pTch = precedence.charAt(Tch) // get precedence TOS char
if (pSch >= pTch) { Stk.push(cmmd); break CommandParse; } // 4c) stack higher than scanned
PostStr += Stk.pop()+’ ‘; // 4d)
} while (0===0);
break;
}
getEl(‘Stack’).value = Stk.join(‘n’);
getEl(‘postStr’).value = PostStr;
if (getEl(‘SglStep’).checked) {
tmp = ‘cmmd,Sch: ‘+cmmd+’:’+pSch + ‘nn TOS,Tch:’+Stk[Stk.length-1]+’:’+pTch;
tmp += ‘nnnPostStr: ‘+PostStr;
if (ALERT(tmp) == false) { break; }
}
} // 6)
while ((Stk.length-1) > -1) { // 7)
Tch = Stk.pop(); if (Tch != ‘(‘) { PostStr += Tch + ‘ ‘; }
}
getEl(‘postStr’).value = PostStr;
return Stk.join(‘n’);
}
/* InFix to PostFix procedure
1) Parse next input element
2) Is it an operand? (like a number or a variable) If yes put it in output.
3) Is it an open bracket “(“? If yes push it in stack.
4) Is it an operator (like +, -, *, /, etc.)? if yes:
a) If the stack is empty, push the operator into the stack
b) If the top of the stack is “(” then push the operator into the stack
c) If the operator priority is higher than the top stack operator one, then push it onto the stack
d) If none of the above is true pop the stack once and goto 4.i
5) Is it a closed bracket “)”?
a) If yes pop the stack until you get the corresponding “(”
b) then discard both the brackets.
6) Is there another input token? If yes goto 1
7) If the stack is not empty just pop the stack until it’s empty.
*/
function ConvertIn2Post() {
getEl(‘Scanned’).value = Step1(getEl(‘inStr’).value);
postStr = ”;
getEl(‘Stack’).value = Step3();
}
</script>
</head>
<body>
<h1>Infix to Postfix Test</h1>
<div style=”float:left;width:300px”>
<button id=’n1′ onClick=”getEl(‘inStr’).value = ‘100 + xvar * 200′”>N1</button>
<button id=’n2’ onClick=”getEl(‘inStr’).value = ‘200 * xvar + 300′”>N2</button>
<button id=’n3’ onClick=”getEl(‘inStr’).value = ‘300 * (xvar+400)'”>N3</button>
<button id=’n4’ onClick=”getEl(‘inStr’).value = ‘(a*(b+c/d))'”>N4</button>
<button id=’n5’ onClick=”getEl(‘inStr’).value = ‘((a*(b+c)/d))'”>N5 extra ‘()'</button>
<br>
<button id=’t1’ onClick=”getEl(‘inStr’).value = ‘Now is the time'”>T1</button>
<button id=’t2’ onClick=’getEl(“inStr”).value = “”Now is the time””‘>T2</button>
<!– produces error –>
<button id=’t3’ onClick=”getEl(‘inStr’).value = ‘”Now is the time”‘”>T3 error</button>
<!– –>
<br>
<button id=’clr’
onClick=”getEl(‘inStr’).value=”;Scan=[];getEl(‘Scanned’).value=”;getEl(‘postStr’).value=””>
Clear</button>
<input type=”checkbox” id=”SglStep” onClick=”Toggle(‘StackDIV’)”> Single Step
<p>
Infix<br>
<input type=”text” id=”inStr” value=”” size=”40″>
<p>
<button onClick=”ConvertIn2Post()”>Convert</button>
<p>
<input type=”text” id=’postStr’ value=” size=”40″>
<br>PostFix
<p>
<div id=”StackDIV” style=”display:none”>
Scanned:<br>
<input type=”text” id=”Scanned” value=” size=”40″”>
Stack<br>
<textarea id=”Stack” rows=”10″ cols=”10″></textarea>
</div>
</div>
<div style=”float:left;padding:5px”>
InFix to PostFix procedure
<ul>
<li> 1) Parse next input element
<li> 2) Is it an operand? (like a number or a variable)
<br> If yes put it in output.
<li> 3) Is it an open bracket “(“? If yes push it in stack.
<ul>
<li> 4) Is it an operator (like +, -, *, /, etc.)? if yes:
<li> a) If the stack is empty, push the operator into the stack
<li> b) If the top of the stack is “(” then push the operator into the stack
<li> c) If the operator priority is higher than the top stack operator one,
<br> then push it onto the stack
<li> d) If none of the above is true pop the stack once and goto 4.i
</ul>
<li> 5) Is it a closed bracket “)”?
<br> If yes pop the stack until you get the corresponding “(”
<br> then discard both the brackets.
<li> 6) Is there another input token? If yes goto 1
<li> 7) If the stack is not empty just pop the stack until it’s empty.
</ul>
</div>
<div style=”clear:both”></div>
</body>
</html>
Any suggestions will be considered.
Neither problem will halt my project, but I would like recognize the special conditions of possible user input
and ignore or notify user of the problem.