First, demand analysis.
1. function: sparse as a line of expression, if the expression is wrong, output "expression error"; Otherwise, the value of the expression is calculated and output. Operators include addition, subtraction, multiplication, division, multiplication and subtraction. Parentheses are parentheses, but they can be nested layer by layer. Operands can be floating-point numbers or variables with multiple letters.
2. Input is in the form of expression, and press Enter to end. The range of input value does not exceed the range of floating-point number. Contains variables with alphabetic names, which are case-insensitive.
3. If the calculation result is an integer, the integer is output; If decimals are included, floating-point numbers are output.
Second, the outline design
1, the overall idea, first read a line of expression and store it in a character array. Then read each word in turn and judge. Read in and calculate. Two stacks are used in the program, a character stack and a number stack, which are used to store operators and numbers respectively, and are calculated according to the priority order of operators. Finally, output the results.
2. This program includes several modules, main functions and several basic functions.
Explain several functions:
Bool stackempty(save 1 s) is used to judge whether the operand stack s is empty.
Invalid push (save1&; S, char e) If the stack is full, output "Stack is full", otherwise put the element e on the stack.
Invalid popup (save1&; S, char & ampe) If the stack is empty, output "stack is empty", otherwise assign the top element of the stack to E.
Bool stackempty2(save2 s) is used to judge whether the operator stack S is empty.
Invalid push 2 (save & amps, char e) If the operator stack is full, output "stack is full"; Otherwise, element e is put on the stack.
Voidpopp2 (save & amps, char & ampe) If the stack is empty, output "stack is empty", otherwise assign the top element of the stack to E.
Int in(char e) returns the priority of operator e in the stack.
Int out(char e) returns the priority of the off-stack operator e.
Void count(char a, char ope, char b) performs corresponding operations on A and B, and puts the operation results on the stack.
3. Specific operation steps:
1. Read a line of expression first and store it with the character array line[].
2. Read and process each character in turn, which is the same as the expression error judgment:
1. If it is a number, continue to judge the next character until the next character is not a number or a decimal point. If the number contains more than two decimal points, it indicates an input error. Otherwise, you can guarantee that the operand is a complete floating-point number, and then put it on the operand stack.
If the number is not the last digit of the expression and there is no "+,-,*,/,)" after it, it is an expression error.
2. For the operator, there are two situations:
1. If the operator is a minus sign (there are two situations when the operator is a symbol: one is that the minus sign is at the beginning, and the other is that the symbol is preceded by a "("), then put the zero into the operand stack first, and then put the minus sign into the operator stack.
2. If the operator is not a minus sign, compare it with the top element of the operator stack:
(1) If the element at the top of the stack has a low priority, the newly entered operator will be put on the stack.
(2) If the top element of the stack has a high priority,
1) pops up an operator from the symbol stack,
2) pop one or two operands from the object stack,
3) Push the operation result into the object stack.
(3) If the priorities are equal, use the input element to pop up and cancel the top element of the stack.
If you put "(,+,-,*,/,"at the end of the expression, the expression is wrong.
If there is no number or variable after "+,-,*,/",the expression is wrong.
3. When encountering an alphabetic variable, continue to judge the next character until the next character is not an alphabetic variable, so as to ensure that the variable is complete, then output "Please enter the value of the variable", and then put the input variable value into the operand stack.
If there is no "+,-,*,/,)" after the variable, the expression is wrong.
4. If the word read is not one of the above situations, it means an error.
3. After reading all the characters, if the expression is correct, it will definitely not contain "("or ")". That is, if the operator stack contains "("or ")", the expression will be wrong. Then consider the case that the expression is correct: the operator stack may be empty, so there must be an operand in the operator stack, which is the final result. If it is not empty, the priority of the remaining operators in the operator stack decreases from the top to the bottom of the stack. So you can pop up an operator from the top of the operator stack, pop up two operands from the operand stack for operation, and then put the operation result into the operand stack until the operator stack is empty. At this point, the only operand left in the operand stack is the operation result.
III. Conclusions and experience
1, experimental conclusion
A), the experiment completed the requirements of the topic, increased the operation of floating-point numbers, and made a mistake.
B) Writing code can basically meet the requirements of programming specifications, and the naming of code variables and the writing of comments can basically be carried out as required.
B) Review the knowledge of queues and stacks in data structures and learn to innovate. In the process of writing code, I learned programming specifications and structured programming.
2. Experimental experience
A) Through this design experiment, I reviewed the knowledge of stack and queue in data structure, was able to design something by myself, and learned the basic steps of the design experiment process. Basically, these problems can be solved in an orderly manner.
B) There are many problems in the experiment that have not been found before. These problems are designed in many aspects, including the previous C++ foundation and the recent knowledge of data structure. Through the design of the experiment, I found my own shortcomings. I am learning the loopholes in my knowledge. I didn't consider the details comprehensively enough, and many details were found through debugging. For example, if you forget to consider the negative sign before the variable at first, look at the whole formula, and there may be some operands left in the stack, so you should continue to calculate. I hope to improve my professional knowledge by making up these loopholes.
C) The problem-solving method in the design process made me understand how to study more effectively. How to study so as not to delay too much time? I also learned the general methods to solve problems: consulting teachers and classmates, using the internet and so on.
D) There were many detours during the experiment. Because the ideas are clear from time to time at the beginning of the design, the solutions to some problems cannot be put forward well. In the design process, the code is always modified repeatedly, and on many issues, the code is not optimal from time to time. I believe that in the future study, with the increase of knowledge, the problem will be gradually solved.
Fourth, the program source code
# include & ltiostream & gt
# include & ltcmath & gt
# include & ltcstdlib & gt
Use namespace std
# Define Max 1000
Structure saving 1
{
Floating point n [max];
int top
} stack 1；
Structural preservation 2
{
char n[MAX]；
int top
} stack2
//stack 1 stores numbers, and stack2 stores operation symbols.
Boolstackempty (save1s)//Determines whether it is empty.
{
if (s.top== - 1)
Returns1;
other
Returns 0;
}
Bool stackempty2(save2 s)// Determines whether it is empty.
{
if (s.top== - 1)
Returns1;
other
Returns 0;
}
Invalid push (save1&; S, float e)// Put e on the stack.
{
if(s.top==MAX- 1)
{
Cout & lt& lt "Stack Full"
Return;
}
s . top++；
s . n[s . top]= e；
}
Invalid push 2 (save & amps, char e)// Put e on the stack.
{
if(s.top==MAX- 1)
{
Cout & lt& lt "Stack Full"
Return;
}
s . top++；
s . n[s . top]= e；
}
Invalid popup (save1&; Standard & Poor's, floating & ampE)// Pop the top element of the stack and save it in E.
{
if(s.top==- 1)
{cout & lt& lt "The stack is empty"
other
{ e = s . n[s . top]； s . top-； }
}
Voidpopp2 (save & amps, char & ampE)///Pop the top element of the stack and save it in E.
{
if(s.top==- 1)
{cout & lt& lt "The stack is empty"
other
{ e = s . n[s . top]； s . top-； }
}
Priority of int in(char e)//e in stack
{
If (e ='-'|| e ='+') returns 2;
If (e =' *' || e ='/') returns 4;
If (e = ='') returns 5;
If(e==' (') returns 0;
If(e==')') returns 7;
return- 1；
}
The priority of int out(char e)//e outside the stack.
{
If (e ='-'|| e ='+') returns1;
If (e =' *' || e ='/') returns 3;
If (e = ='') returns to 6;
If(e==' (') returns 7;
If(e==')') returns 0;
return- 1；
}
Voidcount (float a, charope, float b)// performs the calculation and puts the calculation result on the stack.
{
Floating sum;
if(ope = = '+')sum = a+b；
if(ope = = '-')sum = a-b；
if(ope = = ' * ')sum = a * b；
if(ope = = '/')sum = a/b；
if(ope=='^') sum=pow(a，b)；
push(stack 1，sum)；
}
int main()
{
int i=0，len，j，nofpoint，g = 0； //len indicates the length of the input formula. G indicates whether the characters read are letter variables, numbers and operators.
Floating a, b; //a and B are used to store the operands popped up in the operand stack, which is convenient for substituting into the function for calculation.
Charging line [max], operation, temperature [20];
Cout & lt& lt "Please enter an expression"
CIN & gt； & gt line;
len = strlen(line)；
stack 1 . top =- 1； //Leave the stack empty
stack 2 . top =- 1； //Leave the stack empty
while( 1)
{
g = 0；
If(is digit(line[I])// If the read-in character is a number, continue to judge the next character until the next character is not a number or decimal point, so as to ensure that the operand is a complete decimal, and then put the number into the operand stack.
{
j = 0； g = 1；
nof point = 0； //Record the number of decimal places of stored numbers.
while(is digit(line[I])| | line[I]= = '，')
{
If (line [i] = ='.') nofpoint++;
temp[j++]= line[I]；
i++；
If (i & gt=len) is interrupted;
}
if(nof point & gt； 1 | |(I & lt； Len&&(line [i]! = '-' & amp； & OK [me]! = '+' & amp； & OK [me]! =' *' & amp& amp]! = '/' & amp； & OK [me]! ='^' & amp； & OK [me]! =')')) )
{cout & lt& lt "Error in expression"
temp[j]= ' \ 0 '；
b = atof(temp)；
push(stack 1，b)；
If (i & gt=len) is interrupted;
}
other
{
if(line[I]= = '-' | | line[I]= = '+' | | line[I]= = ' * ' | | line[I]= = '/' | |
Line [I] = '|| Line [I] =' ('|| Line [I] =')//If the read-in character is an operator,
{
g = 1；
if(line[I]= = '(' & amp； & ampI = = len){ cout & lt； & lt "Error in expression"
if(line[I]= = '-' | | line[I]= = '+' | | line[I]= = ' * ' | | line[I]= = '/' | | line[i]=='^')
{
if(I = = len){ cout & lt； & lt "Error in expression"
If ((! isdigit(line[I+ 1])& amp； & amp(! isalpha(line[I+ 1])& amp； & line [i+ 1]! There is no number or variable after =' (')/+,-,*,/",error.
{cout & lt& lt "Error in expression"
}
if(line[I]= = '-' & amp； & amp (I = = 0 || line [I-1] =' (')//operator is a minus sign.
{
push(stack 1，0)；
push2(stack2，line[I])；
i++；
}
other
{//Compare the read operator with the top element of the operator stack and perform the corresponding operation.
if(in(stack 2 . n[stack 2 . top])& lt； out(line[I])| | stack empty 2(stack 2)){ push 2(stack 2，line[I])； i++； }
other
if(in(stack 2 . n[stack 2 . top])= = out(line[I]){ i++； stack 2 . top-； }
other
if(in(stack 2 . n[stack 2 . top])& gt； Out (line [i])
{
pop(stack 1，a)；
pop(stack 1，b)；
pop2(stack2，operate)；
count(b，operate，a)；
}
If (i & gt=len) is interrupted;
}
}
other
{
If(is alpha(line[I])// When the read character is an alphabetic variable.
{
g = 1；
Cout < < "Please enter a variable";
while(isalpha(line[I]){ cout & lt； & lt line [i]; i++； }
The value of cout & lt& lt
CIN & gt； & gtb；
push(stack 1，b)；
If (i & gt=len) is interrupted;
If (line [i]! = '-' & amp； & OK [me]! = '+' & amp； & OK [me]! =' *' & amp& amp]! = '/' & amp； & OK [me]! ='^' & amp； & OK [me]! =')')//Variable followed by "+,-,*,/,)" is wrong.
{cout & lt& lt "Error in expression"
}
}
}
if(g = = 0){ cout & lt； & lt "Error in expression"
}
while(stack2.top！ =-1)/Continue operation after reading until the operator stack is empty.
{
pop(stack 1，a)；
pop(stack 1，b)；
pop2(stack2，operate)；
If (operate = =' ('|| operate = =')')//There are redundant brackets.
{cout & lt& lt "Error in expression"
count(b，operate，a)；
}
cout & lt& ltstack 1 . n[stack 1 . top]& lt； & ltendl
Returns 0;
}