Yea*_*508 5 c++ stack data-structures
我必须将中缀表达式转换为后缀.我的中缀到Postfix代码工作没有任何错误.但我还必须找到错误的中缀表达式.如何解决这个问题呢？
这是我的代码:(我使用了自定义堆栈文件)
#include <iostream>
#include <string>
#include "stacktype.cpp"
using namespace std;
string infixToPostFix(string infix);
int higherPrecedenceValidate(char op1, char op2);
int getPrecedence(char op);
int evaluatePostFix(string postfix);
int main()
{
string infix,postfix;
int result;
cin >> infix;
postfix = infixToPostFix(infix);
cout << postfix <<endl;
result = evaluatePostFix(postfix);
cout << "result: " << result << endl;
}
string infixToPostFix(string infix){
StackType<char> operators;
string postfix;
for(int i = 0; i < infix.size(); i++){
// Checking Operator
if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/'){
while (!operators.IsEmpty() && higherPrecedenceValidate(operators.Top(),infix[i]))
{
postfix = postfix + operators.Top();
operators.Pop();
}
operators.Push(infix[i]);
}
// Checking Operand
else if(infix[i] >= '0' && infix[i] <= '9')
{
postfix = postfix + infix[i];
}
//Checking open bracket
else if(infix[i] == '(' ){
operators.Push(infix[i]);
}
//Checking closing bracket
else if(infix[i] == ')' ){
while (!operators.IsEmpty() && operators.Top() != '(')
{
postfix = postfix + operators.Top();
operators.Pop();
}
// poping the opening bracket
operators.Pop();
}
}
// poping rest of element from the stack..
while (!operators.IsEmpty())
{
postfix = postfix + operators.Top();
operators.Pop();
}
return postfix;
}
int evaluatePostFix(string postfix){
StackType<int> finalNumbers;
for(int i = 0; i < postfix.size(); i++){
// Checking Operator
if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/'){
int resultOfTwoNumber;
int number2 = finalNumbers.Top();
finalNumbers.Pop();
int number1 = finalNumbers.Top();
finalNumbers.Pop();
switch (postfix[i])
{
case '+':
resultOfTwoNumber = number1 + number2;
break;
case '-':
resultOfTwoNumber = number1 - number2;
break;
case '*':
resultOfTwoNumber = number1 * number2;
break;
case '/':
resultOfTwoNumber = number1 / number2;
break;
}
finalNumbers.Push(resultOfTwoNumber);
}
// Checking Operand
else if(postfix[i] >= '0' && postfix[i] <= '9')
{
finalNumbers.Push(postfix[i] - '0');
}
}
return finalNumbers.Top();
}
int higherPrecedenceValidate(char operator1, char operator2)
{
int op1 = getPrecedence(operator1);
int op2 = getPrecedence(operator2);
if(op1 == op2)
return true;
return op1 > op2 ? true: false;
}
int getPrecedence(char op)
{
int weight = 0;
switch(op)
{
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
}
return weight;
}
现在我解决了这个问题.这是我错误的中缀表达式检查代码,中缀为postfix,后缀为结果评估:
#include <iostream>
#include <string>
#include "stacktype.cpp"
using namespace std;
string infixToPostFix(string infix);
int higherPrecedenceValidate(char op1, char op2);
int getPrecedence(char op);
int evaluatePostFix(string postfix);
int main()
{
string infix,postfix;
int result;
cout << "Infix: ";
cin >> infix;
postfix = infixToPostFix(infix);
cout << "\nPostfix: " << postfix << endl << endl;
if(postfix != "Wrong Expression"){
result = evaluatePostFix(postfix);
cout << "Result: " << result << endl << endl;
}
}
string infixToPostFix(string infix){
StackType<char> operators;
bool isMathOperatorRepeated = false;
bool isOperaendRepeated = false;
string postfix;
for(int i = 0; i < infix.size(); i++){
// Checking Operator
if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/'){
if(isMathOperatorRepeated){
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char and add it with postfix string .
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
while (!operators.IsEmpty() && higherPrecedenceValidate(operators.Top(),infix[i]))
{
postfix = postfix + operators.Top();
operators.Pop();
}
operators.Push(infix[i]);
isMathOperatorRepeated = true;
isOperaendRepeated = false;
}
// Checking Operand
else if(infix[i] >= '0' && infix[i] <= '9')
{
if(isOperaendRepeated){
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char and add it with postfix string .
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
postfix = postfix + infix[i];
isMathOperatorRepeated = false;
isOperaendRepeated = true;
}
//Checking open bracket
else if(infix[i] == '(' ){
operators.Push(infix[i]);
isMathOperatorRepeated = false;
isOperaendRepeated = false;
}
//Checking closing bracket
else if(infix[i] == ')' ){
while (!operators.IsEmpty() && operators.Top() != '(')
{
postfix = postfix + operators.Top();
operators.Pop();
}
/*
checking stack beacuse we know
that if the infix char is ')'
and the stack is empty then the infix expression is wrong
*/
if(operators.IsEmpty()){
postfix = "Wrong Expression";
break;
}
else{
operators.Pop();
}
// poping the opening bracket
isMathOperatorRepeated = false;
isOperaendRepeated = false;
}
// checking that infix expression has invalid char
else{
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char in stack.
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
}
// poping rest of element from the stack..
while (!operators.IsEmpty())
{
if(operators.Top() == '('){
postfix = "Wrong Expression";
break;
}
else{
postfix = postfix + operators.Top();
operators.Pop();
}
}
return postfix;
}
int evaluatePostFix(string postfix){
StackType<int> finalNumbers;
for(int i = 0; i < postfix.size(); i++){
// Checking Operator
if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/'){
int resultOfTwoNumber;
int number2 = finalNumbers.Top();
finalNumbers.Pop();
int number1 = finalNumbers.Top();
finalNumbers.Pop();
switch (postfix[i])
{
case '+':
resultOfTwoNumber = number1 + number2;
break;
case '-':
resultOfTwoNumber = number1 - number2;
break;
case '*':
resultOfTwoNumber = number1 * number2;
break;
case '/':
resultOfTwoNumber = number1 / number2;
break;
}
finalNumbers.Push(resultOfTwoNumber);
}
// Checking Operand
else if(postfix[i] >= '0' && postfix[i] <= '9')
{
finalNumbers.Push(postfix[i] - '0');
}
}
return finalNumbers.Top();
}
int higherPrecedenceValidate(char operator1, char operator2)
{
int op1 = getPrecedence(operator1);
int op2 = getPrecedence(operator2);
if(op1 == op2)
return true;
return op1 > op2 ? true: false;
}
int getPrecedence(char op)
{
int weight = 0;
switch(op)
{
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
}
return weight;
}