8
How can I estimate the stack space needed to transform an infix expression into...
source link: https://www.codesd.com/item/how-can-i-estimate-the-stack-space-needed-to-transform-an-infix-expression-into-a-postfix-expression.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
How can I estimate the stack space needed to transform an infix expression into a postfix expression
advertisements
There is the famous shunting-yard algorithm that can be used to turn an infix expression (such as 1 + 2 * 3) into a postfix expression (such as 1 2 2 * +). The shunting-yard algorithm needs a stack to store elements that are about to be moved.
Is it possible to pre-estimate the length of the stack needed to perform a translation of a specific input into its postfix form in linear time and constant memory?
Sure. The shunting-yard algorithm only pushes operators (including parentheses) onto the stack, so a first-order approximation is the number of operators in the expression. With a little more intelligence, you could scan the expression and look for associativity and grouping. But by the time you were done, you would probably have written a stack-based algorithm for determining the best estimate of the stack size required for the expression, and would have doubled your execution cost.
Related Articles
How can I estimate the size of my gzipped script?
How can I estimate the size of my JavaScript file after it is gzipped? Are there online tools for this? Or is it similar to using winzip for example?http://closure-compiler.appspot.com/home lets you paste in code, and it will give you compression rat
How can I estimate the size of an Oracle index?
I'm considering adding an index to an Oracle table, but I'd like to first estimate the size of the index after it has been built (I don't need a precise size - just an estimate.) Supposing I have access to all of the meta-data about the table (number
How can I get the remaining space for common use in a shell script?
Okay so I'm writing a shell script that will need to delete files if available space is running low, however I don't know how to retrieve the remaining space in such a way that quotas will be taken into account (if set). For example, I could use the
How can I ignore the white space in a Moq VerifySet () expression?
I want to verify a string is being set to a specific value in a Moq object. I created a little console application to simulate what I want done. using System; using Moq; namespace MoqVerifySet { public interface MyInterface { string MyValue { get; se
How can I get the free space of a volume in a C program?
Just as the title says, how can I get a volume's free space inside a C program? I am not using tricks like system(), they do not work well. (Why? Well, I already tried it!) I need something like df, unfortunately I didn't find anything in the standar
How can I estimate the variable influence of factors in my model rather than just factor factors?
I created a regression model And i want to estimate an influence analysis for each factor. Meaning take the square Wald-estimation (z-value) for a specific factor and divide it by sum of squares of their Wald-estimation. and that how I estimate the i
How can I set the stack pointer from gdb using JLink and a Cortex M4?
I am using a Segger J-Link Base with gdb on Linux to debug an Atmel SAM4S8C MCU. I have the following in a gdb command file that I specify with the --command argument when starting gdb: target remote localhost:2331 monitor flash device SAM4S8C I also
Java - How can I check the next space in a string? (For IRC Bot)
Obviously, for an IRC bot, input is generated by a user typing a single string, usually with a command and a few arguments, each separated by a space. I am coding an IRC bot using Java and would like to parse arguments that might vary in character le
How can I fill the entire space of a 100% div with 3 divs of the same size?
I have a div.wrap with 100% width and 3 div inside it. I need the 3 div have the same width and could fill all the space of div.wrap. I've tried to do something like that: html: <div class="wrap"> <div></div> <div></di
How can I escape the white space in a list of bash loops?
I have a bash shell script that loops through all child directories (but not files) of a certain directory. The problem is that some of the directory names contain spaces. Here are the contents of my test directory: $ls -F test Baltimore/ Cherry Hill
How can I estimate the entropy content of this entry?
I have a 1KHZ triangle wave generator that I am measuring from a PIC micro controller using the analog input. The frequency source for the triangle wave and the analog capture are separate frequency sources. The ADC captures at 100ksps with 12 [edit:
How can I estimate the file size of an image using its width and height?
I have recently written an image resizing program using php, which works by downloading images off another server, resizing them and saving them to our own. The bad news is that my Hosting account only allows a php memory limit of 64M, and this is ju
How can I extend the mouse space in OpenGL windowed mode
How do I extend the distance the mouse can move in an OpenGL window? What I wish to achieve is an fps like interface where the cursor is hidden and camera rotations are not limited by the mouse having to remain inside the window boundaries.This is of
How can I check the following conditions in c # using a regular expression
I've a condition like this if I enter the text format as 9 - This should only allow numbers s- Should only allow special chars a - should only allow alphabets x - should allow alpha numerics There may be combinations like, if I specify '9s' this shou
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK