Преобразование из инфиксного выражения в постфикс (C ++) с использованием стеков

Таким образом, есть ряд проблем с вашим кодом. Я опубликую, что (должно быть) исправленное решение, в котором есть обильные комментарии, чтобы объяснить, что происходит и где вы допустили ошибки. Несколько вещей заранее:

1. Я буду использовать std::string вместо char * потому что это делает вещи намного чище, и, честно говоря, вы должны использовать его в C++ если у вас нет очень веских причин не делать этого (например, C библиотека). Эта версия также возвращает string вместо того, чтобы взять char * в качестве параметра.

2. Я использую стек из стандартной библиотеки, <stack>, который немного отличается от вашего домашнего проката. top() показывает следующий элемент без удаляя его из стека, и pop() возвращается void, но удаляет верхний элемент из стека.

3. Это бесплатная функция, не являющаяся частью класса, но ее должно быть легко изменить — мне просто проще протестировать этот способ.

4. Я не уверен, что ваши таблицы приоритетов операторов верны, однако я позволю вам проверить это дважды.

#include <stack>
#include <cctype>
#include <iostream>

std::string convertToPostfix(std::string& infix)
{
std::string postfix; //Our return string
std::stack<char> stack;
stack.push('('); //Push a left parenthesis ‘(‘ onto the stack.
infix.push_back(')');

//We know we need to process every element in the string,
//so let's do that instead of having to worry about
//hardcoded numbers and i, j indecies
for(std::size_t i = 0; i < infix.size(); ++i) {

//If it's a digit, add it to the output
//Also, if it's a space, add it to the output
//this makes it look a bit nicer
if(isdigit(infix[i]) || isspace(infix[i])) {
postfix.push_back(infix[i]);
}

//Already iterating over i, so
//don't need to worry about i++
//Also, these options are all mutually exclusive,
//so they should be else if instead of if.
//(Mutually exclusive in that if something is a digit,
//it can't be a parens or an operator or anything else).
else if(infix[i] == '(') {
stack.push(infix[i]);
}

//This is farily similar to your code, but cleaned up.
//With strings we can simply push_back instead of having
//to worry about incrementing some counter.
else if(isOperator(infix[i]))
{
char operator1 = infix[i];
if(isOperator(stack.top())) {
while(!stack.empty() && precedence(operator1,stack.top())) {
postfix.push_back(stack.top());
stack.pop();
}
}
//This shouldn't be in an else - we always want to push the
//operator onto the stack
stack.push(operator1);
}

//We've hit a right parens - Why you had a for loop
//here originally I don't know
else if(infix[i] == ')') {
//While top of stack is not a right parens
while(stack.top() != '(') {
//Insert into postfix and pop the stack
postfix.push_back(stack.top());
stack.pop();
}
// Discard the left parens - you'd forgotten to do this
stack.pop();
}
}

//Remove any remaining operators from the stack
while(!stack.empty()) {
postfix.push_back(stack.top());
stack.pop();
}
}

Вот мое использование C с многозначным вычислением.

#include <stdio.h>
#include <math.h>
#define MAX 50
void push(char[],char);
void in_push(double[], double);
int pop();
int prec(char);
double eval(char[],int,double[]);
int top = 0;
void main() {
double eval_stack[MAX];
int op_count=0;
char stack[MAX], exps[MAX], symbols[MAX];
int i=0,j=0,len,check;
while((symbols[i]=getchar())!='\n') {
if(symbols[i]!=' ' || symbols[i]!='\t') {
if(symbols[i]=='+' || symbols[i]=='-' || symbols[i]=='/' || symbols[i]=='*' || symbols[i]=='^')
op_count++;
i++;
}
}
symbols[i]='#';
symbols[++i]='\0';
len = strlen(symbols);
stack[top] = '#';
for(i=0; i<=len; i++) {
if(symbols[i]>='a'  && symbols[i]<='z') {
exps[j]=symbols[i];
j++;
}
switch(symbols[i]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
//if(symbols[i]>='a'  && symbols[i]<='z') {
exps[j]=symbols[i];
j++;
break;
case '+': case '-': case '*': case '/': case '^':
exps[j++] = ' ';
while(prec(symbols[i]) <= prec(stack[top])) {

exps[j] = stack[top];
pop();
//printf("\n\t\t%d\t\t%d\n", top,j);
j++;}
if(prec(symbols[i]) > prec(stack[top])) {
push(stack,symbols[i]);
}
break;
case '(':
push(stack,symbols[i]);
break;
case ')':
while(stack[top]!='(') {
exps[j] = stack[top];
pop();
j++;

}
pop();
break;
case '#':
exps[j++] = ' ';
while(stack[top]!='#') {
exps[j] = stack[top];
pop();
j++;

}
pop();
break;
}
}
exps[j]='\0';
printf("Postfix: %s", exps);
for(i=0; i<j; i++)
if(exps[i]=='a')
check = 1;
if(check!=1)
printf("\nSolution: %.1f", eval(exps,j,eval_stack));
}

double eval(char exps[],int exps_len,double eval_stack[]) {
int i; int len=exps_len,temp;
double in_temp[MAX],t;
int count,power,j,in_count;
count=power=j=t=in_count=0;
double result;
for(i=0; i<len; i++) {
switch(exps[i]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
in_temp[i] = exps[i]-'0';
j=i+1;
while(exps[j]>='0' && exps[j]<='9') {
in_temp[j] = exps[j]-'0';
j++; // 2
}
count = i; // 3
while(in_temp[count]<='0' && in_temp[count]<='9') {
power = (j-count)-1;
t = t + in_temp[count]*(pow(10,power));
power--;
count++;
}
in_push(eval_stack,t);
i=j-1;
t=0;
break;
case '+':
temp = pop();
pop();
result = eval_stack[temp] + eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '-':
temp = pop();
pop();
result = eval_stack[temp] - eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '*':
temp = pop();
pop();
result = eval_stack[temp] * eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '/':
temp = pop();
pop();
result = eval_stack[temp] / eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '^':
temp = pop();
pop();
result = pow(eval_stack[temp],eval_stack[temp+1]);
in_push(eval_stack,result);
break;
}
}
return eval_stack[top];
}
int prec(char a) {
if(a=='^')
return 3;
else if(a=='*' || a=='/' || a=='%')
return 2;
else if(a=='+' || a=='-')
return 1;
else if(a=='(')
return 0;
else
return -1;
}

void push(char stack[], char ele) {
if(top>=MAX) {
printf("\nStack Overflow");
exit(1);
}
stack[++top] = ele;
}
void in_push(double stack[], double ele) {
if(top>=MAX) {
printf("\nStack Overflow");
exit(1);
}
stack[++top] = ele;
}
int pop() {
if(top<0) {
printf("\nStack Underflow");
exit(1);
}

top = top - 1;
return top;
}

Реализация на C ++ приведена ниже:

  void infix2postfix(string s)
{
stack<char>st;
for(int i=0; i<s.length(); i++)
{
if(isdigit(s[i]) || isalpha(s[i]))  cout<<s[i];
else if( s[i]==')' )
{
while(st.top()!='(')
{
cout<<st.top();
st.pop();
}
st.pop();
}

else st.push(s[i]);
}
}

Приоритет оператора является проблемой в этом случае. Правильный приоритет оператора в порядке убывания:

mul, div, mod   << *, /, % >>
add, sub        << +, - >>
XOR             << ^ >>

В приведенном выше вопросе рассмотрим функцию приоритета

bool ArithmeticExpression::precedence(char operator1, char operator2)
{
if ( operator1 == '^' )
return true;
else if ( operator2 == '^' )
return false;
else if ( operator1 == '*' || operator1 == '/' )
return true;
else if ( operator1 == '+' || operator1 == '-' )
if ( operator2 == '*' || operator2 == '/' )
return false;
else
return true;
return false;
}

для каждого значения в operator1 соответствующее значение operator2 должно быть проверено на приоритетность в соответствии с ТАБЛИЦЕЙ ОПЕРАТОРА, упомянутой выше. Не возвращайте значения без правильного сравнения.