如何查找错误的中缀表达式？
How to find wrong infix expression?
我必须将中缀表达式转换为后缀。我的 Infix to 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;
}
Now I solved this problem. Here is my wrong infix expression checking code with infix to postfix and postfix to result evalution :
#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;
}
在进行转换以确定中缀表达式是否有效时，您应该检查以下几项内容：
- 将最后的
else 添加到确定字符类型的链中，即运算符、数字或括号。当无法识别该字符时，您的代码将命中该分支，这意味着中缀表达式无效。您可能需要添加另一个 "valid" 分支以允许空格。
- 添加检查以查看一个运算符前面是否有另一个运算符，如
2 + * 3 中所示。您可以在 "this is an operator" 分支中设置 bool 标志，然后在其他地方重置。
- 在弹出左括号之前添加检查堆栈是否为空。它上面的
while 循环可能由于两个原因而结束——堆栈变空，或者您找到了相应的左括号。如果因为栈为空导致循环结束，则表达式段的右括号比左括号多，表达式无效。
- 添加一个检查，确保您在堆栈的最后 "unwinding" 中弹出的运算符中有 none 是括号。如果最后在堆栈中发现括号，则表达式的左括号比右括号多，因此它是无效的。
当检测到表达式无效时，抛出异常，或者return一个特殊的string表示转换失败。
我必须将中缀表达式转换为后缀。我的 Infix to 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;
}
Now I solved this problem. Here is my wrong infix expression checking code with infix to postfix and postfix to result evalution :
#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;
}
在进行转换以确定中缀表达式是否有效时，您应该检查以下几项内容：
- 将最后的
else添加到确定字符类型的链中，即运算符、数字或括号。当无法识别该字符时，您的代码将命中该分支，这意味着中缀表达式无效。您可能需要添加另一个 "valid" 分支以允许空格。 - 添加检查以查看一个运算符前面是否有另一个运算符，如
2 + * 3中所示。您可以在 "this is an operator" 分支中设置bool标志，然后在其他地方重置。 - 在弹出左括号之前添加检查堆栈是否为空。它上面的
while循环可能由于两个原因而结束——堆栈变空，或者您找到了相应的左括号。如果因为栈为空导致循环结束，则表达式段的右括号比左括号多，表达式无效。 - 添加一个检查，确保您在堆栈的最后 "unwinding" 中弹出的运算符中有 none 是括号。如果最后在堆栈中发现括号，则表达式的左括号比右括号多，因此它是无效的。
当检测到表达式无效时，抛出异常，或者return一个特殊的string表示转换失败。