Question
I as programming a postfix evaluator, and I was able to do it correctly for single digit number. Now I need an idea of how to do it for multiple digit number, as my current program evaluates a two digit number as different numbers.
Here's the code :
https://stackoverflow.com/questions/22292184
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianpublic class PostfixEvaluation {
public static void main(String[] args) {
String postfix = "23+79*-";
Stack stack = new Stack();
for (int i = 0; i < postfix.length(); i++) {
if (postfix.charAt(i) == '+') {
int v1 = stack.pop();
int v2 = stack.pop();
stack.push(v2 + v1);
} else if (postfix.charAt(i) == '-') {
int v1 = stack.pop();
int v2 = stack.pop();
stack.push(v2 - v1);
} else if (postfix.charAt(i) == '*') {
int v1 = stack.pop();
int v2 = stack.pop();
stack.push(v2 * v1);
} else if (postfix.charAt(i) == '/') {
int v1 = stack.pop();
int v2 = stack.pop();
stack.push(v2 / v1);
} else if (postfix.charAt(i) == '^') {
int v1 = stack.pop();
int v2 = stack.pop();
stack.push((int) Math.pow(v2, v1));
} else {
stack.push((int) postfix.charAt(i) - 48);
}
}
System.out.println(stack.pop());
}
}
Solution
To be able to identify multi-digit numbers, there must be a separator symbol between two numbers.
For example, you can use space as the separator symbol. All the tokens in postfix will be space separated. Your example would become "2 3 + 7 9 * -". You should read one token at a time, not one character.
OTHER TIPS
Conventional logic of evaluation of post-fix expression by stack can solve numbers of only 1 digit i.e. 0-9. This is a very big drawback of the logic used as well as it makes the program of no practical use. By simple change in the method of input into the stack we have removed the problem of single digit integer and now a number of any digit might be used for evaluation. Though my code is done in C you can still follow the algo: http://wowmoron.wordpress.com/2014/11/16/evaluation-of-postfix-expression-containing-multi-digit-integer/
You need to keep track of whether the previous read was a digit. If so and you get another digit, then you should pop the value off the stack, multiply it by 10, add the digit you just read and push it back onto the stack. You will also need to separate digits that belong to different number. On most RPN calculators, there is an "Enter" button for that purpose. So pick a separator for that.
well this may not be the optimal approach but anyways,you have to maintain a num variable that will store the number (will add digit by digit until space is encountered);
~I have not tested it for edge cases yet ~ My code goes like :
#include <iostream>
#include<cmath>
#include<stack>
#include<string.h>
using namespace std;
int prefixEval(string s) {
int n = s.length();
int operand2;
int operand1;
stack < int > st;
for (int i = 0; i <= n - 1; i++) {
int num = 0, mult = 1, numOfDigits = 0, count = 0;
if ((s[i] >= '0' && s[i] <= '9') || s[i] == ' ') {
int j = i;
while (s[j] != ' ') {
count++;
j++;
}
mult = pow(10, count - 1);
while ((s[i] >= '0' && s[i] <= '9') && s[i] != ' ') {
st.push(s[i] - '0');
int temp = st.top();
st.pop();
num = num + mult * temp;
mult /= 10;
i++;
if (s[i] == ' ') {
st.push(num);
break;
}
}
} else {
int operand2 = st.top();
st.pop();
int operand1 = st.top();
st.pop();
switch (s[i]) {
case ('+'):
st.push(operand1 + operand2);
break;
case ('-'):
st.push(operand1 - operand2);
break;
case ('/'):
st.push(operand1 / operand2);
break;
case ('*'):
st.push(operand1 * operand2);
break;
default:
break;
}
}
}
return st.top();
}
int main() {
string s;
getline(cin, s);
cout << prefixEval(s);
}
//You can do it as follows in C programming:
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
int STACK[100];
int top = 0;
int flag = 0;
void push(int item)
{
int MaxStacks = 100;
if (top >= MaxStacks)
{
printf("Overflow\n");
return;
}
else if (flag == 1)
{
int newelem;
newelem = STACK[top];
STACK[top] = item + 10 * newelem;
}
else if (flag == 0)
{
top = top + 1;
STACK[top] = item;
flag = 1;
}
}
int pop()
{
int item;
if (top <= 0)
{
printf("Underflow\n");
}
else
{
item = STACK[top];
top = top - 1;
}
return 0;
}
void evaluate(char elem[])
{
int i;
int A, B;
char ch;
int result;
A = 0;
B = 0;
for (i = 0; elem[i] != ')'; i++)
{
ch = elem[i];
if (isdigit(ch))
{
push(ch - '0');
}
else if (ch == '\n')
{
flag = 0;
}
else if (ch == '+' || ch == '*' || ch == '-' || ch == '/')
{
flag = 0;
A = STACK[top];
pop();
B = STACK[top];
pop();
switch (ch)
{
case '+':
result = B + A;
break;
case '-':
result = B - A;
break;
case '*':
result = B * A;
break;
case '/':
result = B / A;
break;
}
push(result);
}
}
printf("Result of Post fix expression is %d\n", STACK[top]);
}
int main()
{
int i;
char elem[100];
// clrscr();
printf("Enter the elements of the post fix expression\n and enter right
parenthesis ')' at the end of the expression.\n");
for (i = 0; i <= 100; i++)
{
scanf("%c", &elem[i]);
if (elem[i] == ')')
{
break;
}
}
evaluate(elem);
getch();
return 0;
}
