问题：
如何查找错误的中缀表达式？
耿志义
#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;
}
现在我解决了这个问题。以下是我错误的中缀表达式检查代码，中缀到后缀，后缀到结果评估：
#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;
}
共有1个答案
谭新知
在进行转换时，您应该检查以下几点，以确定中缀表达式是否有效：
- 将最后的
els添加到确定字符类型（即运算符、数字或括号）的链中。当字符无法识别时，代码将击中该分支，这意味着中缀表达式无效。您可能需要添加另一个“有效”分支以允许空格。 - 添加一个检查，查看一个运算符前面是否有另一个运算符，如
2+*3中所示。您可以在“this is a operator”分支中设置bool标志，并在其他任何地方重置。 - 在弹出开始方括号之前，添加一个堆栈不为空的检查。它上面的
while循环可能会因为两个原因而结束--堆栈为空，或者找到相应的圆括号。如果循环因堆栈为空而结束，则表达式段的闭括号多于开括号，表达式无效。 - 添加一个检查，以确保在堆栈的最后“解绕”过程中弹出的运算符没有一个是圆括号。如果在堆栈末尾找到一个括号，则表达式的开括号多于闭括号，因此无效。
当检测到表达式无效时，引发异常或返回特殊的字符串以指示转换失败。
类似资料：
-
我需要的算法，将检查是否给定的表达式是中缀，后缀或前缀表达式。我尝试了一种方法，通过检查字符串的第一个或最后两个项，例如。 AB如果字符串的第一个索引中有一个运算符，那么它就是一个前缀 AB如果字符串的最后一个索引中有一个运算符，那么它就是一个后缀 否则它就是一个中缀。 但是感觉不太合适，所以请建议我一个更好的算法。
-
本文向大家介绍中缀表达式转后缀表达式相关面试题，主要包含被问及中缀表达式转后缀表达式时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 对于中缀表达式,遇到操作数直接将其输出,如果遇到操作符和左括号全部压入栈中,若遇到右括号则将栈中元素全部弹出,直到遇到左括号为止。压栈过程中,若遇到其它操作符,从栈中弹出元素直到遇到更低优先级的操作符为止。
-
当你编写一个算术表达式如 B*C 时，表达式的形式使你能够正确理解它。在这种情况下，你知道 B 乘以 C, 因为乘法运算符 * 出现在表达式中。这种类型的符号称为中缀，因为运算符在它处理的两个操作数之间。看另外一个中缀示例，A+B*C，运算符 + 和 * 仍然出现在操作数之间。这里面有个问题是，他们分别作用于哪个运算数上，+ 作用于 A 和 B , 还是 * 作用于 B 和 C？表达式似乎有点模糊
-
我有一份从MS Word复制/粘贴的文件。所有的引文都被复制为，这基本上在我的LaTeX文档中造成了混乱，因此它们必须是。 有没有可能创建一个正则表达式来查找所有这些，其中可以是任何东西（包括符号、数字等）。），并用正确的引号替换它的正则表达式？我使用Sublime文本，它能够直接在编辑器中使用RegEX。
-
New in Django 1.7. 这篇文档是查找 API 的参考，Django 用这些API 构建数据库查询的WHERE 子句。若要学习如何使用 查找，参见执行查询；若要了解如何创建 新的查找，参见自定义查找。 查找 API 由两个部分组成：RegisterLookupMixin 类，它用于注册查找；查询表达式API，它是一个方法集，类必须实现它们才可以注册成一个查找。 Django 有两个
-
使用的到算法： 输入: 预期输出: 实际输出: 如果当前运算符和堆栈顶部的运算符具有优先级，则检查它们的相关性， null null 然而，我的代码不适合于关联。有人能解释一下在上面的实现中如何处理关联性吗？